ぬるぬるの競プロ日記

コードをぬるぬる書きたいです。

ABC115 C - Christmas Eve

初めに思いついたこと:

・最小値だから二分探索では???(条件反射)

ー>問題をよく見ると、そんな必要はない。

 

・N=10^5だからsortして考えて良いな。

ー>sortしたら尺取り法の要領で求まるのでは?

ー>Kが決まっているから尺を取る必要もない。

ー>左端を決めれば右端も自動的に決まる。

 

結果:

sortをして、右端に対して全探索をする。

計算量はsortがボトルネックになってO(N log N)

 

実装:

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

int N, K;
int h[101010];

signed main() {
  cin >> N >> K;
  for (int i = 0; i < N; i++) cin >> h[i];

  sort(h, h + N);

  int ans = INF;
  for (int i = 0; i + K - 1 < N; i++) {
    int tmp = abs(h[i + K - 1] - h[i]);
    chmin(ans, tmp);
  }

  cout << ans << endl;
  return 0;
}