CodeForces - 1337D Xenia and Colorful Gems(二分)

题目链接：点击查看

题目大意：给出三个序列分别记为 a，b，c，现在要求分别从三个序列中找出 x , y , z ，使得 ( x - y )^2 + ( y - z )^2 + ( y - z )^2 最小，求出这个最小值

题目分析：读完题第一反应就是二分嘛，稍微理了一下思路，假设 x <= y <= z ，可以枚举其中一个数组的数作为 y ，然后在另外两个数组中，一个找到小于等于 y 的最大值记为 x ，另一个找大于等于 y 的最小值记为 z ，维护最小值就是答案了

思路非常简单，就是实现起来可能写的比较恶心，这边建议可以将函数封装一下，然后反复调用就好了

一开始想到了 splay 里恰好就有这两个操作，于是就想白嫖，把以前的代码拿下来copy过去，果不其然的TLE了，难顶，然后自己写二分过的，过了四个题之后愉快下班洗漱睡觉，在洗漱的过程中想到了 inf 可能不能作为无穷大，但自己也没法hack掉自己，就懒得在改了，第二天早晨果不其然被fst了，不过还好是小号，不然心态就崩了。。

最后补充一个小技巧，为了防止二分时对边界的判断，在每个数组中加一个 -inf 和 inf 就好了，需要注意的是，因为我的 inf 是0x3f3f3f3f ，在这个题目中不够大，所以在计算 ( x - y )^2 + ( y - z )^2 + ( y - z )^2 的函数中特判一下就行了

代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;LL a[N],b[N],c[N];inline LL get_upper(LL a[],int n,LL x)//在数组a中找到大于等于x的最小值 {int l=0,r=n+1;LL ans;while(l<=r){int mid=l+r>>1;if(a[mid]>=x){ans=a[mid];r=mid-1;}elsel=mid+1;}return ans; }inline LL get_lower(LL a[],int n,LL x)//在数组a中找到小于等于x的最大值 {int l=0,r=n+1;LL ans;while(l<=r){int mid=l+r>>1;if(a[mid]<=x){ans=a[mid];l=mid+1;}elser=mid-1;}return ans; }inline LL fun(LL x,LL y,LL z) {if(x==inf||y==inf||z==inf)//特判infreturn LLONG_MAX;return (x-y)*(x-y)+(x-z)*(x-z)+(y-z)*(y-z); }LL cal(LL a[],int na,LL b[],int nb,LL c[],int nc)//遍历数组a作为y {LL ans=LLONG_MAX;for(int i=1;i<=na;i++){ans=min(ans,fun(a[i],get_lower(b,nb,a[i]),get_upper(c,nc,a[i])));ans=min(ans,fun(a[i],get_upper(b,nb,a[i]),get_lower(c,nc,a[i])));}return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int na,nb,nc;scanf("%d%d%d",&na,&nb,&nc);for(int i=1;i<=na;i++)scanf("%lld",a+i);for(int i=1;i<=nb;i++)scanf("%lld",b+i);for(int i=1;i<=nc;i++)scanf("%lld",c+i);a[0]=b[0]=c[0]=-inf;a[na+1]=b[nb+1]=c[nc+1]=inf;sort(a+1,a+1+na);sort(b+1,b+1+nb);sort(c+1,c+1+nc);printf("%lld\n",min(cal(c,nc,a,na,b,nb),min(cal(a,na,b,nb,c,nc),cal(b,nb,a,na,c,nc))));}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1337D Xenia and Colorful Gems(二分)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。