题面
题意
给定三个数组
要求从每个数组中拿出一个数
问这三个数两两之差的平方和的最小值
解题思路
虽然说是思路，实际上有些瞎搞吧
下面可能会看上去有点乱
对于这种题目，我只知道的结论只有一个：
如果已经固定了两个数 a b ，且保证第三个数 c 在这两个数之间
那么当 c 位于 a b 的正中间时能取到最小值，如果 c 靠近 a 或者 b 的任意一侧，答案值会变大（类似二次函数开口向上图像）
所以，我的想法是，在第一个数组 R 里枚举第一个数，下标为 i （所有下标从0开始，数组已从小到大排序）
在第二个数组 G 里二分查找第一个大于等于 R[i] 的数，下标为 gtmp
那么可能的答案下标就只有 gtmp （大于等于R[i]） 和 gtmp-1（小于R[i]）（如果它们存在的话）
两种情况都考虑一遍，这里以 gtmp 为例
现在已经固定了 R[i] 和 G[gtmp] 两个数
根据上面的结论，我们应该在第三个数组里寻找最靠近 (R[i]+G[gtmp])/2 的数
同样二分查找，获得第一个大于等于这个数的下标，定为 btmp
所以在第三个数组里可能的下标就是 btmp 和 btmp-1
下面再以 btmp 为例
此时可以先拿 R[i] / G[gtmp] / B[btmp] 这三个计算一次答案并取小
但也有可能发生这种情况——
我们上面二分查找 btmp 时，以 (R[i]+G[gtmp])/2 作为索引查找，所以这里假设了 R[i] 和 G[gtmp] 就包含了这三个数的最小值与最大值，而 B[btmp] 应该在这两个值以内
实际上也有可能出现 B[btmp] 在 R[i] ~ G[gtmp] 以外的情况
（这种情况在第4 5这两个样例中都有出现，以第4个样例为例子，枚举到第一个数字是 2 ，最靠近的位于第二个数组中的数字是 3 ，以 (2+3)/2=2 为索引二分出来的最接近的第三个数字是 6 ，很容易发现 6 已经超出了 2~3 这个范围，且如果以 6 为最大值，实际上第二个数字为 4 时才能取到答案的最小值）
所以，我们保持第一个数组 R 的下标 i 固定不变，以此时的 gtmp 作为最值，再次在第二个数组中以 (R[i]+B[btmp])/2 为索引二分，获得新的下标 gtmp2
同样，以 gtmp2 或者 gtmp2-1 作为第二个数组的下标，再计算取一次答案才能考虑完全
以上就是瞎搞想法，详见代码
完整程序
实际上大部分都是复制粘贴
(Pretests: 186ms/3000ms)
(System Tests: 233ms/3000ms)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll LINF=0x3f3f3f3f3f3f3f3f;
ll R[100050],G[100050],B[100050];
inline ll cal(ll a,ll b,ll c)
{
return (a-b)*(a-b)+(a-c)*(a-c)+(b-c)*(b-c);
}
void solve()
{
int nr,ng,nb;
cin>>nr>>ng>>nb;
for(int i=0;i<nr;i++)
cin>>R[i];
for(int i=0;i<ng;i++)
cin>>G[i];
for(int i=0;i<nb;i++)
cin>>B[i];
sort(R,R+nr);
sort(G,G+ng);
sort(B,B+nb);
ll ans=LINF;
int gtmp,btmp,gtmp2;
for(int i=0;i<nr;i++) //枚举第一个数组中的下标 i
{
gtmp=lower_bound(G,G+ng,R[i])-G; //以R[i]为索引二分查找第二个数组中第一个大于等于的数字下标
if(gtmp<ng) //gtmp下标如果合法
{
btmp=lower_bound(B,B+nb,(R[i]+G[gtmp])>>1)-B; //以(R[i]+G[gtmp])/2为索引二分第三个数字下标btmp
if(btmp<nb) //btmp下标如果合法
{
ans=min(ans,cal(R[i],G[gtmp],B[btmp])); //计算一次此时的答案
gtmp2=lower_bound(G,G+ng,(R[i]+B[btmp])>>1)-G; //固定i和btmp，以(R[i]+B[btmp])/2为索引重新二分寻找第二个数字下标gtmp2
if(gtmp2<ng)
ans=min(ans,cal(R[i],G[gtmp2],B[btmp])); //合法时计算答案，下同
if(gtmp2>0)
ans=min(ans,cal(R[i],G[gtmp2-1],B[btmp]));
}
if(btmp>0) //btmp-1下标如果合法
{
ans=min(ans,cal(R[i],G[gtmp],B[btmp-1]));
gtmp2=lower_bound(G,G+ng,(R[i]+B[btmp-1])>>1)-G;
if(gtmp2<ng)
ans=min(ans,cal(R[i],G[gtmp2],B[btmp-1]));
if(gtmp2>0)
ans=min(ans,cal(R[i],G[gtmp2-1],B[btmp-1]));
}
}
if(gtmp>0)//gtmp-1下标如果合法
{
btmp=lower_bound(B,B+nb,(R[i]+G[gtmp-1])>>1)-B;
if(btmp<nb)
{
ans=min(ans,cal(R[i],G[gtmp-1],B[btmp]));
gtmp2=lower_bound(G,G+ng,(R[i]+B[btmp])>>1)-G;
if(gtmp2<ng)
ans=min(ans,cal(R[i],G[gtmp2],B[btmp]));
if(gtmp2>0)
ans=min(ans,cal(R[i],G[gtmp2-1],B[btmp]));
}
if(btmp>0)
{
ans=min(ans,cal(R[i],G[gtmp-1],B[btmp-1]));
gtmp2=lower_bound(G,G+ng,(R[i]+B[btmp-1])>>1)-G;
if(gtmp2<ng)
ans=min(ans,cal(R[i],G[gtmp2],B[btmp-1]));
if(gtmp2>0)
ans=min(ans,cal(R[i],G[gtmp2-1],B[btmp-1]));
}
}
}
cout<<ans<<'
';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin>>T;
for(int t=1;t<=T;t++)
solve();
return 0;
}