Xenia and Colorful Gems（思维+二分/双指针）Codeforces Round #635 (Div. 2)

题目大意

       有三个数组，分别从每个数组中挑一个数字形成$x,y,z$x,y,z，问$(x-y)^2+(y-z)^2+(z-x)^2$(x−y)2+(y−z)2+(z−x)2的最小值为多少？

分析过程

       这个题目有$3$3个变量，容易想到的思路是固定其中一个再去确定其他两个。这里我们固定$y$y，我们发现其实答案无非就是6种情况（根据$x,y,z$x,y,z的大小关系划分）。我们不妨先假设取出来的$x,y,z$x,y,z满足约束$x\leq y\leq z$x≤y≤z，这个时候我们会发现，这种限定下的答案是可以计算的，当$y$y一定时，不论$z$z取什么，$x$x的值一定是越大越好，因此这个时候$x$x等于$r$r数组中$\leq y$≤y的最大值，是确定的；然后当$x,y$x,y确定之后，我们会发现$z$z的值应该越小越好，因此$z$z也能被确定。所以对于$x\leq y\leq z$x≤y≤z这种情形，我们只需要枚举$y$y，然后定义双指针枚举$x,z$x,z的值即可，时间复杂度为$O(n)$O(n)。这只是一种情形，然后我们把$6$6种情形都跑一遍，更新$ans$ans即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
typedef long long ll;
ll n_r, n_g, n_b, r[maxn], g[maxn], b[maxn], ans;
void cal(ll n_r, ll n_g, ll n_b, ll r[], ll g[], ll b[]){
	ll x, y, z, i, j = 1, k = 1;
	for(i=1;i<=n_g;++i){ //枚举y 
		y = g[i];
		while(r[j] <= y && j <= n_r) ++j;
		if(j == 1) continue;
		--j;
		x = r[j];
		while(b[k] < y) ++k;
		if(k > n_b) break;
		z = b[k];
		ans = min(ans, (x - y) * (x - y) + (y - z) * (y - z) + (z - x) * (z - x));
	}
}
void solve(){
	ans = 0x7fffffffffffffff;
	cal(n_r, n_g, n_b, r, g, b);
	cal(n_r, n_b, n_g, r, b, g);
	cal(n_g, n_r, n_b, g, r, b);
	cal(n_g, n_b, n_r, g, b, r);
	cal(n_b, n_g, n_r, b, g, r);
	cal(n_b, n_r, n_g, b, r, g);
	cout<<ans<<'\n';
}
int main(){
	int t, i, j;
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--){
		cin>>n_r>>n_g>>n_b;
		for(i=1;i<=n_r;++i) cin>>r[i];
		for(i=1;i<=n_g;++i) cin>>g[i];
		for(i=1;i<=n_b;++i) cin>>b[i];
		sort(r+1, r+1+n_r);
		sort(g+1, g+1+n_g);
		sort(b+1, b+1+n_b);
		solve();
	}
	return 0;
}