D. Xenia and Colorful Gems（二分）JokerHe的博客-

题目传送门

题意： 给你na个红色糖，nb个绿色糖，nc个蓝色糖，每一块糖都有自己的一个权值，每种颜色拿一个，使得(x-y)² + (x-z)² +(y-z)² 尽可能小，x,y,z表示三块糖的权值。

思路： 我们知道选出的三块糖有 x<=y<=z （只看数值，不看颜色） ，那么我们枚举所有糖果，作为中间的这个，然后在另外两种糖果中分别找一个大于等于y、小于y的，最后算最小值就行了。

#include<bits/stdc++.h> #define endl 'n' #define null NULL #define ls p<<1 #define rs p<<1|1 #define fi first #define se second #define mp make_pair #define pb push_back #define ll long long #define int long long #define vi vector<int> #define mii map<int,int> #define pii pair<int,int> #define ull unsigned long long #define all(x) x.begin(),x.end() #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.n"; char *fs,*ft,buf[1<<20]; #define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++; inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();} return x*f;} using namespace std; const int N=2e5+5; const int inf=0x7fffffff; const int mod=998244353; const double eps=1e-6; int a[N],b[N],c[N]; int check(int i,int j,int k) { //  cout<<i<<' '<<j<<' '<<k<<endl; return (a[i]-b[j])*(a[i]-b[j])+(a[i]-c[k])*(a[i]-c[k])+(c[k]-b[j])*(c[k]-b[j]); } signed main() { int t;     cin>>t; while(t--) { int na,nb,nc;         cin>>na>>nb>>nc; for(int i=1;i<=na;i++)             cin>>a[i]; for(int i=1;i<=nb;i++)             cin>>b[i]; for(int i=1;i<=nc;i++)             cin>>c[i]; sort(a+1,a+na+1);sort(b+1,b+nb+1);sort(c+1,c+nc+1); int res=2e18; for(int i=1;i<=na;i++) { int pb=lower_bound(b+1,b+nb+1,a[i])-b; int pc=lower_bound(c+1,c+nc+1,a[i])-c; if(pb==nb+1)                 pb--; if(pc==nc+1)                 pc--;             res=min(res,check(i,pb,pc)); if(pb!=1)                 res=min(res,check(i,pb-1,pc)); if(pc!=1)                 res=min(res,check(i,pb,pc-1)); if(pb!=1&&pc!=1)                 res=min(res,check(i,pb-1,pc-1)); } for(int i=1;i<=nb;i++) { int pa=lower_bound(a+1,a+na+1,b[i])-a; int pc=lower_bound(c+1,c+nc+1,b[i])-c; if(pa==na+1)                 pa--; if(pc==nc+1)                 pc--;             res=min(res,check(pa,i,pc)); if(pa!=1)                 res=min(res,check(pa-1,i,pc)); if(pc!=1)                 res=min(res,check(pa,i,pc-1)); if(pa!=1&&pc!=1)                 res=min(res,check(pa-1,i,pc-1)); } for(int i=1;i<=nc;i++) { int pb=lower_bound(b+1,b+nb+1,c[i])-b; int pa=lower_bound(a+1,a+na+1,c[i])-a; if(pb==nb+1)                 pb--; if(pa==na+1)                 pa--;             res=min(res,check(pa,pb,i)); if(pb!=1)                 res=min(res,check(pa,pb-1,i)); if(pa!=1)                 res=min(res,check(pa-1,pb,i)); if(pb!=1&&pa!=1)                 res=min(res,check(pa-1,pb-1,i)); }         cout<<res<<endl; } }