题解 AT4280 【[ABC115C] Christmas Eve】

Zirnc · 2020-02-19 12:34:35 · 题解

ChungZH's blog · ChungZH's portfolio

在另一个世界中，今天是平安夜。

高叶先生的花园里种了 N 棵树。 第 i 棵树的高度 (1 \leq i \leq N)为 h_i 米。

他决定从这些树中选择 K 棵树，并用电灯装饰它们。 为了使风景更美，装饰树的高度应尽可能彼此靠近。

更具体地说，让最高装饰树的高度为 h_{max} 米，让最低装饰树的高度为 h_{min} 米，

我们可以先把 h 数组从小到大排序。然后每次装饰 k 个相邻的树，计算这 k 个树中最左和最右的树的高度相差多少，然后和 minn 比较一下，记录最小值即可。

#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;
}