51nod 1267 4个数和为0

基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题

给出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

二分 
存下每两个数的和 然后二分
屠龙宝刀点击就送

#include <algorithm>

#include <cstdlib>

#include <cstdio>

#define mo 20047

#define mo2 13831

using namespace std;

struct node

{

    int x,y,z;

    bool operator<(node a)const

    {

        return z<a.z;

    }

}h[];

int A[],cnt,n;

int main()

{

    scanf("%d",&n);

    if(n<) {printf("No");return ;}

    for(int i=;i<=n;i++) {scanf("%d",&A[i]);}

    for(int i=;i<=n;i++)

    {

        for(int j=i+;j<=n;j++)

        {

            h[++cnt].x=A[i];

            h[cnt].y=A[j];

            h[cnt].z=A[i]+A[j];

        }

    }

    sort(h+,h++cnt);

    int l=,r=cnt;

    while(l<r-)

    {

        int mid=(l+r)>>;

        if(h[l].z+h[r].z==&&h[l].x!=h[l].y&&h[r].x!=h[l].x&&h[r].y!=h[l].y&&h[l].x!=h[r].y&&h[l].y!=h[r].x)

            {printf("Yes");return ;}

        if(h[l].z+h[r].z>) r--;

        else if(h[l].z+h[mid].z<) l++;

        else if(h[l].z+h[mid].z) break;

    }

    printf("No");

    return ;

}