题目
给出 N 个整数, 你来判断一下是否能够选出 4 个数, 他们的和为 0, 可以则输出 "Yes", 否则输出 "No".
n<=1e3
思路
《挑战程序设计竞赛》的经典题, 预处理两层 + 二分
代码
- #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;
- }
来源: http://www.bubuko.com/infodetail-3138052.html