自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 22:45:03，当前版本为作者最后更新于2018-04-07 16:10:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[yLOI2023] B 苦竹林

Description

给定一个数列 $a$，找到最小的 $\varepsilon$，使得 $a$ 存在一个长度为 $m$ 的子数列（可以不连续）$b$，满足对任何的 $1 \leq i, j \leq m$，都有 $|b_i - b_j| \leq \varepsilon$。

$2 \leq m \leq n \leq 10^5$，$1 \leq a_i \leq 10^9$。

Analysis

算法一

当 $m = 2$ 时，只要找到数列里差值最小的两个数；当 $m = n$ 时，只要找到数列里最大值与最小值的差。分别可得 $10$ 分。

算法二

枚举所有选 $b$ 的方案。一共有 $\binom{n}{m}$ 种方案，枚举方案可以搜索，也可以二进制枚举。对每种方案，对应的 $\varepsilon$ 就是该方案里 $b$ 的最大值减去最小值，可以 $O(m)$ 算出。总时间复杂度 $O(m \times \binom{n}{m})$。期望得分 $40$ 分。

算法三

当 $a_i$ 有序时，容易发现答案对应的 $b$ 数列一定是数列里一个连续的子段。因为答案一定是 $b$ 数列里最大值减去最小值，而与中间的数无关。所以所选的数应该越紧凑越好。对一个确定的 $b$ 数列最小值，如果所选的数中间有空隙，则会令最大值有增大的可能，导致答案遍劣。

于是 $O(n)$ 枚举 $a$ 里每个长度为 $m$ 的子区间，当区间左端点为 $i$ 时，区间最小值就是 $a_i$，最大值是 $a_{i + m - 1}$。可以 $O(1)$ 算出此时的 $\varepsilon$ 并与当前算出的答案作比较。

时间复杂度 $O(n)$，期望得分 $60$ 分。

算法四

注意到 $a$ 的顺序其实并不影响答案。因为我们考虑的是 $b$ 里每一对数，而并不考虑他们之间的前后关系。

于是当 $a$ 无序时，把 $a$ 排个序按照算法三完成即可。

如果没有认识到区间最大值就是右端点，区间最小值就是左端点，求最值可以 $O(m)$ 扫一遍区间。时间复杂度 $O(nm)$，期望得分 $80$ 分。

如果会 $O(1)$ 求最值，且使用冒泡排序、插入排序等 $O(n^2)$ 的排序，算法的时间复杂度为 $O(n^2)$，期望得分 $80$ 分；如果采用 std::sort 等时间复杂度为 $O(n \log n)$ 的排序，则算法的时间复杂度为 $O(n \log n)$，期望得分 $100$ 分。

Code

#include <climits>
#include <vector>
#include <iostream>
#include <algorithm>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, m;
  std::cin >> n >> m;
  std::vector<int> a(n);
  std::generate(a.begin(), a.end(), []() { int x; std::cin >> x; return x; });
  int ans = INT_MAX;
  std::sort(a.begin(), a.end());
  for (int l = 0, r = m - 1; r < n; ++l, ++r) {
    ans = std::min(ans, a[r] - a[l]);
  }
  std::cout << ans << std::endl;
}

Generator

void makedata(int T) {
  int n = 100000, m, lim = 1000000000;
  if (T <= 4) n = 5;
  else if (T <= 8) n = 1000;
  if (T == 1) m = 2;
  else if (T == 2) m = n;
  else m = modx(n) + 1;
  std::vector<int> a(n);
  std::generate(a.begin(), a.end(), [&]() { return modx(lim) + 1; });
  if (T <= 6) std::sort(a.begin(), a.end());
  printf("%d %d\n", n, m);
  for (int i = 0; i < n; ++i) printf("%d%c", a[i], " \n"[i == n-1]);
}