AtCoder题解｜ABC 115C Christmas Eve

题目信息 📚

【题目描述】

In some other world, today is Christmas Eve.

There are $N$ trees planted in Mr. Takaha’s garden. The height of the $i$-th tree $(1 \leq i \leq N)$ is $h_i$ meters.

He decides to choose $K$ trees from these trees and decorate them with electric lights. To make the scenery more beautiful, the heights of the decorated trees should be as close to each other as possible.

More specifically, let the height of the tallest decorated tree be $h_{\text{max}}$ meters, and the height of the shortest decorated tree be $h_{\text{min}}$ meters. The smaller the value of $h_{\text{max}} - h_{\text{min}}$ is, the better. What is the minimum possible value of $h_{\text{max}} - h_{\text{min}}$?

【输入】

The input is given from Standard Input in the following format:

$N$ $K$

$h_1$

$h_2$

$\vdots$

$h_N$

【输出】

Print the minimum possible value of $h_{\text{max}} - h_{\text{min}}$.

【数据范围】

$2 \leq K < N \leq 10^5$
$1 \leq h_i \leq 10^9$
$h_i$ is an integer.

【输入样例1】

【输出样例1】

If we decorate the first, third, and fifth trees, $h_{\text{max}} = 12$, $h_{\text{min}} = 10$ so $h_{\text{max}} - h_{\text{min}} = 2$. This is optimal.

【输入样例2】

【输出样例2】

If we decorate the second, fourth, and fifth trees, $h_{\text{max}} = 7$, $h_{\text{min}} = 7$ so $h_{\text{max}} - h_{\text{min}} = 0$. This is optimal.

There are not too many trees in these sample inputs, but in the actual problem, there can be up to one hundred thousand trees (it’s just not feasible to put a sample with a hundred thousand lines here).

【题目来源】

https://atcoder.jp/contests/abc115/tasks/abc115_c

题目解析 🍉

【题目分析】

此题与 Codeforces 1537C 比较像，均需要求若干个数组元素的最小差值。

只需要排序，然后求相邻差值即可。

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, k, h[N];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入数据并且排序
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> h[i];
    sort(h + 1, h + n + 1);

    // 枚举最小值
    int ans = INT_MAX;
    for (int i = 1; i + k - 1 <= n; i++) {
        ans = min(ans, h[i + k - 1] - h[i]);
    }
    cout << ans << endl;

    return 0;
}