[yLOI2023] B 苦竹林
一扶苏一
·
·
题解
[yLOI2023] B 苦竹林
Description
给定一个数列 a，找到最小的 \varepsilon，使得 a 存在一个长度为 m 的子数列（可以不连续）b，满足对任何的 1 \leq i, j \leq m，都有 |b_i - b_j| \leq \varepsilon。
## 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
```cpp
#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
```cpp
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]);
}
```