D. Xenia and Colorful Gems （排序&贪心)

D. Xenia and Colorful Gems （排序&贪心)

题目传送门

思路：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
int a[3][N];
ll cal(int i,int j,int k){
	return (ll)(a[0][i]-a[1][j])*(a[0][i]-a[1][j])+(ll)(a[1][j]-a[2][k])*(a[1][j]-a[2][k])+(ll)(a[0][i]-a[2][k])*(a[0][i]-a[2][k]);
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int cnt[3];
		for(int i=0;i<3;i++) scanf("%d",&cnt[i]);
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<cnt[i];j++)
			{
				scanf("%d",&a[i][j]);
			}
			sort(a[i],a[i]+cnt[i]);
		}
		ll ans=3e18;
		int i=0,j=0,k=0;
		while(i<cnt[0]-1||j<cnt[1]-1||k<cnt[2]-1)//向内收缩. 
		{
			ans=min(ans,cal(i,j,k));
			ll tmp[3];
			tmp[0]=cal(i+1,j,k),tmp[1]=cal(i,j+1,k),tmp[2]=cal(i,j,k+1);
			ll mn=3e18;
			if(i<cnt[0]-1) mn=min(mn,tmp[0]);
			if(j<cnt[1]-1) mn=min(mn,tmp[1]);
			if(k<cnt[2]-1) mn=min(mn,tmp[2]);
			if(i<cnt[0]-1&&mn==tmp[0]) i++; //贪心思想,不断向内收缩. 
			else if(j<cnt[1]-1&&mn==tmp[1]) j++;
			else if(k<cnt[2]-1&&mn==tmp[2]) k++;
		}
		ans=min(ans,cal(i,j,k));//没有收缩的情况. 
		printf("%lld\n",ans);
	}
	return 0;
}