B title: razlika priority queue approach

subject

My solution is to use the priority queue to reduce the complexity when calculating the minimum later . The point is to simulate the smallest difference , So all the difference push Go to the priority queue , And then one by one “ Probe ”, If you meet someone who is not inside pop In this way, it can be simplified into O（n), Although it looks like a double cycle .

#include <bits/stdc++.h>
#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
#define pii pair<int,int>
using namespace std;
const int N=2e6+5;
int a[N];
int d[N];
priority_queue<pii,vector<pii>,greater<pii> > q;
int pqd[N];
void work(){
	int n,k;
	cin>>n>>k;
	rep(i,1,n){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	d[1]=0;
	rep(i,2,n){
		d[i]=a[i]-a[i-1];
	}
	int cnt=0;
	int sum=0,mi=0,xiao=INT_MAX,mii=INT_MAX;
	rep(i,2,n-k){
		q.push({d[i],i});
	}
	rep(i,2,k+1){
		sum=a[i+n-k-1-1]-a[i-1];
		q.push({d[i+n-k-1],i+n-k-1});
		while (!q.empty()){
			if (!(i<=q.top().second&&q.top().second<=i+n-k-1)){
				q.pop();
			}
			else{
				xiao=q.top().first;
				break;
			}
		}
	//	cout<<sum<<"  "<<xiao<<endl;
		mii=min(mii,sum+xiao);
	}
	cout<<mii;
}
signed main(){
	CIO;
	work();
	return 0;
}