题解 AT4280 【[ABC115C] Christmas Eve】
Zirnc
2020-02-19 12:34:35
[ChungZH's blog](https://chungzh.cn) · [ChungZH's portfolio](https://chungzh.cc)
> 在另一个世界中，今天是平安夜。
>
> 高叶先生的花园里种了 $N$ 棵树。 第 $i$ 棵树的高度 $(1 \leq i \leq N)$为 $h_i$ 米。
>
> 他决定从这些树中选择 $K$ 棵树，并用电灯装饰它们。 为了使风景更美，装饰树的高度应尽可能彼此靠近。
>
> 更具体地说，让最高装饰树的高度为 $h_{max}$ 米，让最低装饰树的高度为 $h_{min}$ 米，
>
> $h_{max}-h_{min}$ 值越小越好。$h_{max}-h_{min}$ 的最小可能值是多少？
我们可以先把 $h$ 数组从小到大排序。然后每次装饰 $k$ 个相邻的树，计算这 $k$ 个树中最左和最右的树的高度相差多少，然后和 $minn$ 比较一下，记录最小值即可。
```cpp
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
int h[N + 3];
for (int i = 1; i <= N; i++) {
cin >> h[i];
}
sort(h + 1, h + 1 + N);
int minn = 1e9;
for (int i = 1; i <= N - K + 1; i++) minn = min(minn, h[i + K - 1] - h[i]);
cout << minn << endl;
return 0;
}
```