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

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

2019-04-15

AtCoder ABC 115 C - Christmas Eve (灰色, 300 点)

AtCoder AtCoder300点 ABC-C ソート数列探索順序を工夫して解く最大値と最小値の差を扱う問題 N個からK個を選ぶ設定の問題灰色diff 【問題集】ソートソート:要素の差について考えやすい形にするそのまま覚えたい易しい教育的典型問題最小コスト最大スコア最適化問題最適化テク:最適解の形を考える

今の 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;
}