题目
给出N个整数,你来判断一下是否能够选出4个数,他们的和为0,可以则输出"Yes",否则输出"No"。 n<=1e3
思路
《挑战程序设计竞赛》的经典题,预处理两层+二分
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| #include<bits/stdc++.h> #define ll long long using namespace std; ll n,a[1020],ct; struct E{ ll w; int p1,p2; }e[600020]; int cmp(E x,E y){ return x.w<y.w; } int main(){ scanf("%lld",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ e[++ct]=(E){a[i]+a[j],i,j}; } } sort(e+1,e+1+ct,cmp); for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ int l=1,r=ct,mid; while(l<=r){ mid=(l+r)>>1; if(a[i]+a[j]+e[mid].w<0){ l=mid+1; } else{ r=mid-1; } } for(int k=l;a[i]+a[j]+e[k].w==0;k++){ if(i!=e[k].p1&&i!=e[k].p2&&j!=e[k].p1&&j!=e[k].p2){ printf("Yes\n"); return 0; } } } } printf("No\n"); return 0; }
|