51Nod 1267 4个数和为0 二分

给出N个整数，你来判断一下是否能够选出4个数，他们的和为0，可以则输出"Yes"，否则输出"No"。
Input
第1行，1个数N，N为数组的长度(4 <= N <= 1000)
第2 - N + 1行：A[i]（-10^9 <= A[i] <= 10^9)
Output
如果可以选出4个数，使得他们的和为0，则输出"Yes"，否则输出"No"。
Input示例
5
-1
1
-5
2
4
Output示例
Yes
思路：
二分
第一次是枚举前两个数，后面两个数二分
第二次做法是，先统计出两个不同数的和的数组，然后直接二分

思路一：

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 typedef long long ll;
 5 ll ans[1005];
 6 int main() {
 7     ios::sync_with_stdio(false);
 8     int n,flag=0;
 9     cin>>n;
10     for(int i=0;i<n;++i) cin>>ans[i];
11     sort(ans,ans+n);
12     for(int i=0;i<n;++i) {
13         if(ans[i]>=0) break;
14         for(int j=i+1;j<n;++j) {
15             int l=j+1,r=n-1;
16             while(j<r) {
17                 ll temp=ans[i]+ans[j]+ans[l]+ans[r];
18                 if(temp>0) r--;
19                 else if(temp<0) l++;
20                 else {
21                     flag=1;
22                     cout<<"Yes"<<endl;
23                     return 0;
24                 }
25             }
26         }
27     }
28     if(!flag) cout<<"No"<<endl;
29     return 0;
30 }

View Code

思路二：

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 typedef long long ll;
 5 struct node {
 6     ll sum,x,y;
 7     node() {sum=x=y=0;}
 8 };
 9 node bns[1000005];
10 ll ans[1005];
11 bool cmp(const node &a, const node &b) {
12     if(a.sum<b.sum) return true;
13     if(a.sum>b.sum) return false;
14     if(a.x<b.x) return true;
15     if(a.x>b.x) return false;
16     if(a.y<=b.y) return true;
17     else return false;
18 }
19 int main() {
20     ios::sync_with_stdio(false);
21     int n,ins=0;
22     cin>>n;
23     for(int i=0;i<n;++i) cin>>ans[i];
24     for(int i=0;i<n;++i) {
25         for(int j=i+1;j<n;++j) {
26             bns[ins].sum=ans[i]+ans[j];
27             bns[ins].x=ans[i];
28             bns[ins].y=ans[j];
29             ins++;
30         }
31     }
32     sort(bns,bns+ins,cmp);
33     int l=0,r=ins-1,flag=0;
34     while(l<r) {
35         ll temp=bns[l].sum+bns[r].sum;
36         if(temp<0) l++;
37         else if(temp>0) r--;
38         else {
39             if(bns[l].x!=bns[r].x&&bns[l].y!=bns[r].x&&bns[l].y!=bns[r].y) {
40                 cout<<"Yes"<<endl;
41                 flag=1;
42                 return 0;
43             }
44             l++;
45             r--;
46         }
47     }
48     if(!flag) cout<<"No"<<endl;
49     return 0;
50 }

View Code