题目链接
翻译
给你3种颜色的宝石, 每种宝石数量为nr, ng, nb。
然后依次给出这3中宝石的各个重量。
让你选出来3个宝石, 每种类型的宝石各一个。
假设选出来的A, B, C宝石的重量分别为X, Y, Z。
则要求 ((X-Y)^2+(X-Z)^2+(Y-Z)^2) 的值最小。
让你求出来可能的最小值。
题解
一开始的想法, 就是把这nr + ng + nb个宝石一起排个序, 然后选择相邻的3个宝石就好。
但是一开始枚举的方法错了, 想着枚举最重的那个宝石, 然后前面两个宝石, 紧跟着它的重量。
类似3个指针i, j , k。 然后i是红色宝石的下标, j是绿色宝石的下标, k是蓝色宝石的下标(这里三个类型的宝石
的重量都预先排了个序)。
只要满足r[i] <= g[j] <= b[k]就好了, 当然j是最大的满足g[j] <= b[k]的j, i也是类似的定义。
但是这里就很有问题了。。
实际上应该要满足的是, 你去 固定j的下标 , 然后i(i<=j)尽可能地靠近j, 然后k(j<=k)也尽可能地靠近j。
这样 ((X-Y)^2+(X-Z)^2+(Y-Z)^2) 这个值才是最小的。
但是, 还 不能确定i,j,k具体是哪种颜色宝石的下标, 有可能红色宝石在最优的方案里面是最中间的那个。
所以写个next_permutation(a+0,a+3)这样, 全排列一下(i,j,k)是哪种颜色宝石的下标。
代码
#include<bits/stdc++.h>
#define ll long long
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
using namespace std;
const int N = 2e5;
int T,cnt[3];
int a[3][N+10];
int order[3];
ll sqr(int x){
return 1LL*x*x;
}
int main(){
#ifdef LOCAL_DEFINE
freopen("D:\rush.txt","r",stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
cin >> T;
while (T--){
rep1(i,0,2) cin >> cnt[i];
rep1(i,0,2){
rep1(j,1,cnt[i]){
cin >> a[i][j];
}
sort(a[i]+1,a[i]+1+cnt[i]);
}
rep1(i,0,2){
order[i] = i;
}
ll ans = -1;
do{
int i = 1,j = 1,k = 1;
while (j <= cnt[order[1]]){
while (i+1 <= cnt[order[0]] && a[order[0]][i+1] <= a[order[1]][j]){
i++;
}
while (k+1 <= cnt[order[2]] && a[order[2]][k] < a[order[1]][j]){
k++;
}
if (a[order[0]][i] <= a[order[1]][j] && a[order[1]][j] <= a[order[2]][k]){
int x = a[order[0]][i], y = a[order[1]][j], z = a[order[2]][k];
//cout << x << " " << y << " " << z << endl;
ll temp = sqr(y - x) + sqr(z - x) + sqr(z - y);
if (ans == -1){
ans = temp;
}else{
ans = min(ans, temp);
}
}
j++;
}
}while (next_permutation(order,order+3));
cout << ans << endl;
}
return 0;
}