けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 115 C - Christmas Eve (300 点)

今の 300 点に比べると少し易しめで、でも 300 点っぽくていい感じだなと。

問題へのリンク

問題概要

 N 個の整数  a_1, a_2, \dots, a_N が与えられる。ここから  K 個の整数を選ぶ。

「選ばれた数の最大値と最小値の差」の最小値を求めよ。

制約

  •  2 \le K <  N \le 10^{5}

考えたこと

すごく 300 点問題っぽくていい感じ。ソートして

  •  0 番目と  K-1 番目の差
  •  1 番目と  K 番目の差
  •  2 番目と  K+1 番目の差
  • ...

のうちの最小値を求めれば OK。

たったそれだけの問題ではあるけれど、最初にとりあえず数列をソートしてしまう、というのは多くの問題において重要なステップになるイメージがある。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int N, K; cin >> N >> K;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // ソート
    sort(a.begin(), a.end());

    // K 差の最小値
    long long res = 1LL<<60; // INF の気持ち
    for (int i = 0; i+K-1 < N; ++i) res = min(res, a[i+K-1] - a[i]);
    cout << res << endl;
}