传送门
文章目录
题意：
给你三个数组a,b,ca,b,ca,b,c，让你从每个数组中选择一个数x,y,zx,y,zx,y,z，使得(x−y)2+(x−z)2+(y−z)2(x-y)^2+(x-z)^2+(y-z)^2(x−y)2+(x−z)2+(y−z)2最小，求这个最小值。
思路：
由于答案一定是x≤y≤zx\le y\le zx≤y≤z的形式(当然这里的x,y,zx,y,zx,y,z与题意的x,y,zx,y,zx,y,z不同)，所以我们就可以跑一个3!3!3!排列，让他们分别为x,y,zx,y,zx,y,z，让后枚举其中一个二分另外俩就行了。
具体实现可以写个函数就比较方便了。
我这里写的是枚举xxx，让后分两种即找yyy和找zzz，如果找yyy的话，假设现在已经有x≤yx\le yx≤y了，那么找的zzz根据平方的性质，最好是x+(y−x)/2x+(y-x)/2x+(y−x)/2附近的位置，二分找即可，对于zzz同理。
总结：这个题瞎搞都能过。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const LL inf
=0x3f3f3f3f3f3f3f3f;
const double eps
=1e-6;int n1
,n2
,n3
;
LL a
[N
],b
[N
],c
[N
];LL
get(int i
,int j
,int k
) {return (a
[i
]-b
[j
])*(a
[i
]-b
[j
])+(a
[i
]-c
[k
])*(a
[i
]-c
[k
])+(b
[j
]-c
[k
])*(b
[j
]-c
[k
]);
}LL
solve() {LL ans
=inf
;for(int i
=1;i
<=n1
;i
++) {int val1
=a
[i
];int pos1
=lower_bound(b
+1,b
+1+n2
,val1
)-b
;if(pos1
<=n2
) {int pos2
=lower_bound(c
+1,c
+1+n3
,a
[i
]+(b
[pos1
]-a
[i
])/2)-c
;if(pos2
<=n3
) ans
=min(ans
,get(i
,pos1
,pos2
)); pos2
--;if(pos2
>=1) ans
=min(ans
,get(i
,pos1
,pos2
));}pos1
++;if(pos1
<=n2
) {int pos2
=lower_bound(c
+1,c
+1+n3
,a
[i
]+(b
[pos1
]-a
[i
])/2)-c
;if(pos2
<=n3
) ans
=min(ans
,get(i
,pos1
,pos2
)); pos2
--;if(pos2
>=1) ans
=min(ans
,get(i
,pos1
,pos2
));}pos1
-=2;if(pos1
>=1) {int pos2
=lower_bound(c
+1,c
+1+n3
,b
[pos1
]+(a
[i
]-b
[pos1
])/2)-c
;if(pos2
<=n3
) ans
=min(ans
,get(i
,pos1
,pos2
)); pos2
--;if(pos2
>=1) ans
=min(ans
,get(i
,pos1
,pos2
));}pos1
=lower_bound(c
+1,c
+1+n3
,val1
)-c
;if(pos1
<=n3
) {int pos2
=lower_bound(b
+1,b
+1+n2
,a
[i
]+(c
[pos1
]-a
[i
])/2)-b
;if(pos2
<=n2
) ans
=min(ans
,get(i
,pos2
,pos1
)); pos2
--;if(pos2
>=1) ans
=min(ans
,get(i
,pos2
,pos1
));}pos1
++;if(pos1
<=n3
) {int pos2
=lower_bound(b
+1,b
+1+n2
,a
[i
]+(c
[pos1
]-a
[i
])/2)-b
;if(pos2
<=n2
) ans
=min(ans
,get(i
,pos2
,pos1
)); pos2
--;if(pos2
>=1) ans
=min(ans
,get(i
,pos2
,pos1
));}pos1
-=2;if(pos1
>=1) {int pos2
=lower_bound(b
+1,b
+1+n2
,c
[pos1
]+(a
[i
]-c
[pos1
])/2)-b
;if(pos2
<=n2
) ans
=min(ans
,get(i
,pos2
,pos1
)); pos2
--;if(pos2
>=1) ans
=min(ans
,get(i
,pos2
,pos1
));}}return ans
;
}int main()
{
int _
; scanf("%d",&_
);while(_
--) {scanf("%d%d%d",&n1
,&n2
,&n3
);for(int i
=1;i
<=n1
;i
++) scanf("%lld",&a
[i
]);for(int i
=1;i
<=n2
;i
++) scanf("%lld",&b
[i
]);for(int i
=1;i
<=n3
;i
++) scanf("%lld",&c
[i
]);sort(a
+1,a
+1+n1
); sort(b
+1,b
+1+n2
); sort(c
+1,c
+1+n3
);n1
=unique(a
+1,a
+1+n1
)-a
-1;n2
=unique(b
+1,b
+1+n2
)-b
-1;n3
=unique(c
+1,c
+1+n3
)-c
-1;printf("%lld\n",solve());}return 0;
}
总结
以上是生活随笔为你收集整理的Codeforces Round #635 (Div. 2) D. Xenia and Colorful Gems 暴力 + 二分的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
