HDU 4334 Trouble （暴力）

时间：2022-09-26 16:12:47
Time Limit: 5000MS   Memory Limit: 32768KB   64bit IO Format: %I64d & %I64u

Submit Status

Description

Hassan is in trouble. His mathematics teacher has given him a very difficult problem called 5-sum. Please help him. 
The 5-sum problem is defined as follows: Given 5 sets S_1,...,S_5 of n integer numbers each, is there a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0?
 

Input

First line of input contains a single integer N (1≤N≤50). N test-cases follow. First line of each test-case contains a single integer n (1<=n<=200). 5 lines follow each containing n integer numbers in range [-10^15, 1 0^15]. I-th line denotes set S_i for 1<=i<=5.
 

Output

For each test-case output "Yes" (without quotes) if there are a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0, otherwise output "No".
 

Sample Input

2
2
1 -1
1 -1
1 -1
1 -1
1 -1
3
1 2 3
-1 -2 -3
4 5 6
-1 3 2
-4 -10 -1
 

Sample Output

No
Yes
 

Source

2012 Multi-University Training Contest 4

题意：给定五个集合，每个集合有n个数，从每个集合各取一个数使和为0。如果能输出Yes，不能则输出No。

　　　　看了网上的题解有很多解法，个人感觉这题暴力就能过。

　　　　首先将一二两个集合合并为数组a，再将三四两个集合合并数组b，然后进行从小到大排序，

　　　　设第五个数组为数组c，依次遍历c中的每一个数，看在a，b中是否存在两个数的和与c中的数的和为0，

　　　　将数组a，b进行sort排序，然后一个正序即从小到大遍历，一个逆序从大到小遍历，

　　　　如果三个数的和小于0，a数组后移一位，否则b后移一位。

　　　　这题WA了两次，第一次WA后发现else if用的是三个i，忘了改成i，j，k了。

　　　　第二次WA后发现Yes输出成了YES，No输出成了NO。

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

long long a[],b[],c[],d[],e[],f[],g[];

long long i,j,x,k,l,n,t,flag=,p;

int main()

{

    scanf("%lld",&t);

    while(t--)

    {

        flag=;

        //输入

        scanf("%lld",&n);

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

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

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

        scanf("%lld",&e[i]);

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

        scanf("%lld",&f[i]);

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

        scanf("%lld",&g[i]);

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

        scanf("%lld",&c[i]);

        //合并

        int cnt1=;

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

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

            a[cnt1++]=d[i]+e[j];

        int cnt2=;

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

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

            b[cnt2++]=f[i]+g[j];  //三四合并

        sort(a,a+cnt1);

        sort(b,b+cnt2);

        //计算

        for(i=;i<n;i++) //第五个数组 c[]

        {

            j=;

            k=cnt2-;

             while(j<cnt1 && k>=)

             {

                 if(a[j]+b[k]+c[i]==0LL)

                 {

                     flag=;

                     break;

                 }

                 else if(a[j]+b[k]+c[i]<)

                     j++;

                 else

                     k--;

             }

        }

        if(flag) cout<<"Yes"<<endl;

        else cout<<"No"<<endl;

    }

    return ;

}

相关文章