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

Input

Output

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
");
72     }
73     else
74     {
75         printf("No
");
76     }
77     return 0;
78 }