はまやんはまやんはまやん

hamayanhamayan's blog

解説

https://beta.atcoder.jp/contests/abc115/submissions/3744746

パッと見ると割と難しい問題に見える。
今回は入力をソートしても解くのに問題無いので、ソートしておく。
困ったら全探索をまずは考えるのだが、hminを全探索することにする。
hminがi番目の要素であるとすると、最適なhmaxはi+K-1番目の要素になる。
なので、hminを固定するとhmaxが1つに決まる。
よって、hminを全探索して、hmax-hminの最小値を見ていけば良い。
以下の実装ではL=hminのindex, R=hmaxのindexで実装している。

int N, K, H[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> H[i];
    sort(H, H + N);
 
    int ans = inf;
    rep(L, 0, N - K + 1) {
        int R = L + K - 1;
        chmin(ans, H[R] - H[L]);
    }
    cout << ans << endl;
}