题意：
给出 (3) 个序列各有：(n_r,n_g,n_g) 个。现在在每个序列中选择一个数：(x,y,z)，使得 ((x-y)^2+(x-z)^2+(y-z)^2) 最小，求出该最小值。
数据范围：(1≤n_r,n_g,n_b≤10^5,1≤r_i≤10^9,1≤g_i≤10^9,1≤b_i≤10^9)
分析：
1.官方题解思路：
首先，大概思路是：枚举一个值，然后可以求出另外两个。
假定：(r_ileq g_i leq b_i)，那么 (r_i) 和 (b_i) 必然是越接近 (g_i) ，整个的值越小。因此，可以借助二分来求出 (r_i) 和 (b_i)。
按照分析，有六种可能的排列顺序，枚举进行处理即可。
反思：大概思路想到了，但就是没有想到可以按顺序取分情况处理。
2.其他思路：
每次都向最优的状态转移。
代码 (1)：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int r[N],g[N],b[N];
ll ans;
ll get(int x,int y,int z)
{
return 1LL*(x-y)*(x-y)+1LL*(x-z)*(x-z)+1LL*(y-z)*(y-z);
}
void solve(int a[],int c[],int d[],int x,int y,int z)
{
for(int i=1;i<=y;i++)
{
int t1=lower_bound(a+1,a+1+x,c[i])-a;
int t2=lower_bound(d+1,d+1+z,c[i])-d;
if(t1>x||t1<=x&&a[t1]>c[i])
t1--;
if(t1>=1&&t1<=x&&t2>=1&&t2<=z)
{
ll res=get(a[t1],c[i],d[t2]);//cout<<"res="<<res<<endl;
ans=min(ans,res);
}
}
}
int main()
{
int t,nr,ng,nb;
scanf("%d",&t);
while(t--)
{
ans=3e18;
scanf("%d%d%d",&nr,&ng,&nb);
for(int i=1;i<=nr;i++)
scanf("%d",&r[i]);
for(int i=1;i<=ng;i++)
scanf("%d",&g[i]);
for(int i=1;i<=nb;i++)
scanf("%d",&b[i]);
sort(r+1,r+1+nr);
sort(g+1,g+1+ng);
sort(b+1,b+1+nb);
for(int i=1;i<=6;i++)
{
if(i==1)
solve(r,g,b,nr,ng,nb);
else if(i==2)
solve(b,g,r,nb,ng,nr);
else if(i==3)
solve(g,r,b,ng,nr,nb);
else if(i==4)
solve(b,r,g,nb,nr,ng);
else if(i==5)
solve(g,b,r,ng,nb,nr);
else
solve(r,b,g,nr,nb,ng);
}
printf("%lld
",ans);
}
return 0;
}
代码 (2)：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int r[N],g[N],b[N];
ll ans;
ll get(int x,int y,int z)
{
return 1LL*(x-y)*(x-y)+1LL*(x-z)*(x-z)+1LL*(y-z)*(y-z);
}
int main()
{
int t,nr,ng,nb;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&nr,&ng,&nb);
for(int i=1;i<=nr;i++)
scanf("%d",&r[i]);
for(int i=1;i<=ng;i++)
scanf("%d",&g[i]);
for(int i=1;i<=nb;i++)
scanf("%d",&b[i]);
sort(r+1,r+1+nr);
sort(g+1,g+1+ng);
sort(b+1,b+1+nb);
ans=get(r[1],g[1],b[1]);
int i=1,j=1,k=1;
while(i<=nr&&j<=ng&&k<=nb)
{
ll t1=3e18,t2=3e18,t3=3e18;
if(i+1<=nr)
t1=get(r[i+1],g[j],b[k]);
if(j+1<=ng)
t2=get(r[i],g[j+1],b[k]);
if(k+1<=nb)
t3=get(r[i],g[j],b[k+1]);
ll res=min(t1,min(t2,t3));
ans=min(ans,res);
if(res==t1) i++;
else if(res==t2) j++;
else k++;
}
printf("%lld
",ans);
}
return 0;
}