初めに思いついたこと:
・最小値だから二分探索では???(条件反射)
ー>問題をよく見ると、そんな必要はない。
・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;
}