51 nod 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示例

Output示例

Yes

刚开始使用算出两个数的和然后保存在数组中，将4sum将为2sum，因为在算两个数的和的时候，可能存在重复的情况，所以用if语句判断了一下

#include<stdio.h>

#include<algorithm>

#include<string.h>

const int M = ;

using namespace std;

typedef pair<int, int> P;

int main()

{

    int n, Count, flage;

    int i, j;

    int b[M], a[M];

    P p[M];

    scanf("%d", &n);

    memset(a, , sizeof(a));

    memset(b, , sizeof(b));

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

    {

        scanf("%d", &a[i]);

    }

    Count = ;

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

    {

        p[Count].first = a[i];

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

        {

            p[Count].second = a[j];

            b[Count++] = a[i] + a[j];

        }

    }

    for( i = ; i < Count; i++ )

    {

        for( j = ; j < Count; j++ )

        {

            if(p[i].first != p[j].first && p[i].second !=p[j].second && p[i].first != p[j].second && p[i].second != p[j].first)

            {

                flage = b[i] + b[j];

                if(flage == )

                {

                    printf("Yes\n");

                    return ;

                }

            }

        }

    }

    printf("No\n");

    return ;

}

结果提交的时候过了一半的数据，另外的一半被卡住了

Ac代码

#include <cstdio>

#include <cstdlib>

#include <algorithm>

using namespace std;

const int MAXN =  + ;

int n, num[MAXN];

int main(){

    freopen("in.txt", "r", stdin);

    int flag, tmp;

    while(scanf("%d", &n) != EOF){

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

            scanf("%d", &num[i]);

        }

        sort(num+, num+n);

        flag = ;

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

            if(flag){ break; }

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

                if(flag){ break; }

                int l = j+, r = n-;

                while(l < r){

                    tmp = num[i] + num[j] + num[l] + num[r];

                    if(tmp == ){

                        flag = ;

                        break;

                    }else if(tmp > ){

                        r--;

                    }else{

                        l++;

                    }

                }

            }

        }

        if(flag){

            printf("Yes\n");

        }else{

            printf("No\n");

        }

    }

    return ;

}

巴特西

51 nod 1267 4个数和为0

最新文章

热门文章