Codeforces Round #635 (Div. 2)D. Xenia and Colorful Gems移动开发hrd535523596的博客-

传说门
刚好今晚是中国场！
其实这道题比较水，但当时思路错，一心想着化简公式，浪费了好多时间a.a

题意：三个数组，求(x-y)(x-y)+(x-z)(x-z)+(y-z)*(y-z)的最小值

题解：6nlogn，先sort三个数组a,b,c, 六次枚举二分查找，再每次min找最小值，例如:先固定数组a，再在数组b,c中利用lower_bound找到第一个大于等于a[i]的数，

#pragma GCC optimize(2) #include <bits/stdc++.h> #define ll long long #define endl  'n' using namespace std; const int manx=1e5+5;  ll t,a1,b1,c1; ll a[manx],b[manx],c[manx]; ll checks(ll a[],ll a1,ll b[],ll b1,ll c[],ll c1) {     ll add=2e18,x,y,z; for(int i=1; i<=a1; i++) {         x=a[i];         ll k=lower_bound(b+1,b+b1,x)-b; if(k>=1&&k<=b1&&b[k]>=x) //确保数组b中有比大于等于x的值             y=b[k]; else continue;         ll l=lower_bound(c+1,c+c1,x)-c; if(l>=1&&l<=c1&&c[l]<=x)             z=c[l]; else continue;                      ll d=(y-z)*(y-z)+(x-y)*(x-y)+(x-z)*(x-z);         add=min(add,d); } return add; } int main() {  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);      t;  cin>>t; while(t--) {         cin>>a1;         cin>>b1;         cin>>c1; for(int i=1;i<=a1;i++)             cin>>a[i]; for(int i=1;i<=b1;i++)             cin>>b[i]; for(int i=1;i<=c1;i++)             cin>>c[i]; sort(a+1,a+1+a1); sort(b+1,b+1+b1); sort(c+1,c+1+c1);         ll ans=2e18;         ans=min(ans,checks(a,a1,b,b1,c,c1));ans=min(ans,checks(a,a1,c,c1,b,b1));         ans=min(ans,checks(b,b1,a,a1,c,c1));ans=min(ans,checks(b,b1,c,c1,a,a1));         ans=min(ans,checks(c,c1,b,b1,a,a1));ans=min(ans,checks(c,c1,a,a1,b,b1));         cout<<ans<<endl; } }