Xenia and Colorful Gems
思路
总共有三组数,要求 ((x−y)^2+(y−z)^2+(z−x)^2) 最小值,我们不妨设 a 在第一组数里面,b 在第二组数里面,c 在第三组数里面。
共有如下几种情况
- (a <= b <= c)
- (a <= c <= b)
- (b <= a <= c)
- (b <= c <= a)
- (c <= a <= b)
- (c <= b <= a)
我们考虑枚举中间的数,然后让两边的数趋近于它,这样最后得到的结果就一定满足条件。
这里用lowered_bound来确定,大于等于的数。
用upper_bound返回的指针减一来确定小于等于的数。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
long long get(ll x, ll y, ll z) {
return (x - y) * (x - y) + (y - z) * (y - z) + (z - x) * (z - x);
}
int main() {
// freopen("in.txt", "r", stdin);
int t;
scanf("%d", &t);
while(t--) {
vector<int> a[3];
int n[3];
for(int i = 0; i < 3; i++) {
scanf("%d", &n[i]);
a[i].resize(n[i]);
}
for(int i = 0; i < 3; i++) {
for(int j = 0; j < n[i]; j++)
scanf("%d", &a[i][j]);
sort(a[i].begin(), a[i].end());
}
ll ans = 0x3f3f3f3f3f3f3f3f;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
for(int k = 0; k < 3; k++) {//保证j <= i <= k;
if(i == j || i == k || j == k) continue;
for(vector<int> :: iterator p1 = a[i].begin(); p1 != a[i].end(); p1++) {
auto p2 = lower_bound(a[j].begin(), a[j].end(), *p1);
auto p3 = upper_bound(a[k].begin(), a[k].end(), *p1);
p3--;
if(p3 >= a[k].begin() && p2 < a[j].end())
ans = min(ans, get(*p1, *p2, *p3));
}
}
printf("%lld
", ans);
}
return 0;
}