\(A\) の要素のうち \(K\) 個消すという操作は、 \(A\) の要素のうち \(N-K\) 個残して \(B\) とすると言い換えられます。
このもとで、 ( \(B\) の最小値 ) となる要素をひとつ決め打つことを考えてみましょう。これを \(A_x\) とします。
( \(B\) の最大値 ) \(-\) ( \(B\) の最小値 ) をなるべく小さくするには、 \(A\) の要素であって \(A_x\) 以上のものを小さい方から \(N-K\) 個残すのが最善です。
このことは、 \(A\) を昇順にソートして連続する \(N-K\) 個を残すのが最善であると言い換えることができます。

このもとで、以下の解法が成立します。

• まず、 \(A_1 \le A_2 \le \dots \le A_N\) を満たすように \(A\) をソートする。
• このとき、 \(A_{l+(N-K)-1}-A_l\) のうち \(1 \le l \le K+1\) での最小値が答えである。
  • \(A_l\) を ( \(B\) の最小値 ) と決め打って、連続する \(N-K\) 個の要素を残す場合に対応します。

これは、ソートと for ループを用いることで実装できます。全体で時間計算量 \(O(N \log N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> a(n);
  for(auto &nx : a){cin >> nx;}

  sort(a.begin(),a.end());
  int res=2e9;
  for(int i=0;i<=k;i++){
    res=min(res,a[i+(n-k)-1]-a[i]);
  }
  cout << res << "\n";
  return 0;
}