Codeforces Round 914 (Div. 2)

C. Array Game

题意：给定一个n的数组以及k的操作数，每次可以选择下表为i，j（i<j）得到一个abs（a[i]-a[j]）的数放在数组末尾，问你k次操作后，数组中最小的数是多少？

思路：首先k>=3 选相同的下表两次，一定结果是0，是最小。

k==1 遍历出下表两两相减的绝对值最小以及本身数组中最小的即可

k==2 要将数相减的结果存入数组，然后再暴力两两相减取最小的既可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
	int n,k;
	cin>>n>>k;
	vector<int>a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	if(k>=3){
		cout<<0<<"\n";
		return;
	}
	sort(a.begin(),a.end()); 
	vector<int>b;
	for(int i=1;i<n;i++){
		for(int j=0;j<i;j++){
			b.push_back(abs(a[j]-a[i]));
		}
	}
	sort(b.begin(),b.end());
	if(k==1){
		int t=min(a[0],b[0]);
		cout<<t<<"\n";
		return;
	}
    if(k==2){
	   int mi=min(a[0],b[0]);
	   int m=b.size();
	   a.push_back(1e18+10);
	   int r=0;
	   for(int i=0;i<m;i++){
	   	  while(r<=n&&a[r]<b[i])r++;
	   	  if(r>=1)mi=min(mi,abs(b[i]-a[r-1]));
	   	  mi=min(mi,a[r]-b[i]);
	   }
	   cout<<mi<<"\n";
	}
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t=1;
	cin>>t;
	for(int i=1;i<=t;i++)solve();
	return 0;
}