AtCoder ABC 361 C - Make Them Narrow (4Q, 灰色, 250 点)

めっちゃ面白い問題！！　実はよく似た類題として次の問題がある！

atcoder.jp

• 問題へのリンク

問題概要

長さが の数列 が与えられる。この数列から 個の要素を削除する。

残った数からなる数列中の、最大値と最小値の差の最小値を求めよ。

制約

• 

考えたこと

「 個削除する」というのは、「 個選び出す」と捉えた方が考えやすいので、そう考えることにしよう。改めて とおく。

直観的には、数列 をソートした場合において、「連続する 個を選ぶ」とする場合にみ考えればよいと思われる。このことを一応検証してみよう。数列 はソート済みであるとしよう。

数列 から選ぶ要素のうちの最小値 を固定して考えてみるとハッキリする。このとき、 から 個選んだときの最大値をなるべく小さくしたい。そうすると、 からスタートして小さい順に 個選べばよいことがわかる。

まとめると、 を小さい順に並べた上で、 の値の最小値を求めればよい。計算量は となる。

コード

#include <bits/stdc++.h>
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());
    long long res = A.back() - A[0];
    for (int i = 0; i + (N - K) - 1 < N; ++i) {
        long long diff = A[i + (N - K) - 1] - A[i];
        res = min(res, diff);
    }
    cout << res << endl;
}