4個數的和為0 51nod 1267

給出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"。      

5
-1
1
-5
2
4      

Yes

解題思路：這道題被歸納在排序和二分的目錄下，我們就試着通過排序和二分來解決這題。從n個數中找4個和為0的數,可以先将這些數兩兩組合，這樣得
到的數升序排序，通過二分查找，找到和為0的組合。不過這種算法隻能勉強算為二分吧。      

1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define maxs 1010
 5 int num[maxs];
 6 struct node
 7 {
 8     int x;
 9     int y;
10     int sum;
11 }a[maxs*maxs];
12 int my_cmp(node a,node b)
13 {
14     return a.sum<b.sum;
15 }
16 using namespace std;
17 int main()
18 {
19     int n,i,j,flag;
20     int k=0;
21     flag=0;
22     scanf("%d",&n);
23     for(i=1;i<=n;i++)
24     {
25         scanf("%d",&num[i]);
26         for(j=1;j<i;j++)
27         {
28             a[k].x=i;
29             a[k].y=j;
30             a[k].sum=num[i]+num[j];
31             k++;
32         }
33     }
34     sort(a,a+k,my_cmp);
35     i=0;
36     j=k-1;
37     while(i<k)
38     {
39         if(a[i].sum+a[j].sum==0)
40         {
41           if(a[i].x!=a[j].x&&a[i].x!=a[j].y&&a[i].y!=a[j].x&&a[i].y!=a[j].y)
42           {
43               flag=1;
44               break;
45           }
46           if(a[i].sum==a[i+1].sum)
47           {
48               i++;
49           }
50           else if(a[j].sum==a[j-1].sum)
51           {
52               j--;
53           }
54           else
55           {
56               i++;
57               j--;
58           }
59         }
60         else if(a[i].sum+a[j].sum<0)
61         {
62             i++;
63         }
64         else 
65         {
66             j--;
67         }
68     }
69     if(flag)
70     {
71         printf("Yes\n");
72     }
73     else
74     {
75         printf("No\n");
76     }
77     return 0;
78 }      

作者：王陸