题解：P13416 [COCI 2012/2013 #4] RAZLIKA

滑动窗口。

首先我们将数组排序。

然后剩下有 $N-K$ 个数。

我们需要在长度为 $N-K$ 的滑动窗口中找到最小的相邻差值。

可以使用双端队列来维护滑动窗口中的最小差值，最大差值会等于窗口首尾元素的差值。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,a[1145140],cz[1145140],ans=1e9;
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	int sz=n-k;
	for(int i=1;i<n;i++)cz[i]=a[i+1]-a[i];
	deque<int> q;
	for(int i=1;i<n;i++){
		while(q.size()&&q.front()<=i-(sz-1))q.pop_front();
		while(q.size()&&cz[i]<=cz[q.back()])q.pop_back();
		q.push_back(i);
		if(i>=sz-1){
            int st=i-(sz-1)+1;
            int M=a[st+sz-1]-a[st],m=cz[q.front()];
            ans=min(ans,M+m);
        }
	}
	cout<<ans;
	return 0;
}