【競プロ】1日1AC : ABC115 C問題

今日で5日目です。毎日問題を解くのも習慣化してきました。

今日の問題はこちらです。

Difficultyは232(灰)です。
AtCoder Problemsより)

いつものことですが、是非先に問題を解いてから読み進めてください。

提出コードと考えたこと

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> h(n);
    for(int i = 0;i < n;i++) cin >> h[i];
    sort(h.begin(),h.end());
    set<int> g;
    for(int i;i < n - k + 1;i++){
        g.insert(h[i + k - 1] - h[i]);
    }
    cout << *begin(g) << endl;
    return 0;
}

入力される \(N \) が大きいので、すべての木の選び方を試すのは時間内にできません。同じくらいの高さの木を選べば \( h_{max} - h_{min} \) は小さくなるので、まずは \( h_1,h_2, \cdots ,h_N \) をソートします。

\( h_{max} - h_{min} \) が最小になるのは、高さでソートされた木から連続する \( K \) を選ぶ時なので、このようなすべての場合を試します。
(\( K \) 本選ぶときに1本でも飛ばすと、\( h_{max} - h_{min} \) の値は変わらない、あるいは大きくなることがわかるでしょう)

今回は思いつきでsetを使って最小値を出しましたが、当然配列を使ってもいいです。(何を使うのが一般的なんでしょうか?)

終わりに

今日の問題は思ったよりもすんなり解けてよかったです。早解きも意識して演習に取り組もうと思います。

コメント