首页 > 代码库 > 51nod 1267 4个数和为0

51nod 1267 4个数和为0

2024-09-13 23:06:10   216人阅读

基准时间限制：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-11-524
Output示例
Yes


二分 
存下每两个数的和 然后二分
屠龙宝刀点击就送
#include <algorithm>#include <cstdlib> #include <cstdio>#define mo 20047#define mo2 13831using namespace std;struct node{    int x,y,z;    bool operator<(node a)const    {        return z<a.z;    }}h[1000001];int A[1001],cnt,n;int main(){    scanf("%d",&n);    if(n<3) {printf("No");return 0;}     for(int i=1;i<=n;i++) {scanf("%d",&A[i]);}    for(int i=1;i<=n;i++)    {        for(int j=i+1;j<=n;j++)        {            h[++cnt].x=A[i];            h[cnt].y=A[j];            h[cnt].z=A[i]+A[j];        }    }    sort(h+1,h+1+cnt);    int l=1,r=cnt;    while(l<r-1)    {        int mid=(l+r)>>1;        if(h[l].z+h[r].z==0&&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 0;}        if(h[l].z+h[r].z>0) r--;         else if(h[l].z+h[mid].z<0) l++;        else if(h[l].z+h[mid].z) break;    }    printf("No");    return 0;}
 
51nod 1267 4个数和为0






























        

            
                
                  
                
                

                    联系

                    我们