hdu-2141-Can you find it?

喜欢ヅ旅行 2022-05-28 13:14 102阅读 0赞

# Can you find it? #

**Time Limit: 10000/3000 MS (Java/Others)    Memory Limit: 32768/10000 K (Java/Others)  
Total Submission(s): 37442    Accepted Submission(s): 9153**

Problem Description

Give you three sequences of numbers A, B, C, then we give you a number X. Now you need to calculate if you can find the three numbers Ai, Bj, Ck, which satisfy the formula Ai+Bj+Ck = X.

Input

There are many cases. Every data case is described as followed: In the first line there are three integers L, N, M, in the second line there are L integers represent the sequence A, in the third line there are N integers represent the sequences B, in the forth line there are M integers represent the sequence C. In the fifth line there is an integer S represents there are S integers X to be calculated. 1<=L, N, M<=500, 1<=S<=1000. all the integers are 32-integers.

Output

For each case, firstly you have to print the case number as the form "Case d:", then for the S queries, you calculate if the formula can be satisfied or not. If satisfied, you print "YES", otherwise print "NO".

Sample Input

3 3 31 2 31 2 31 2 331410

Sample Output

Case 1:NOYESNO

题目大意：给出三个数组和一个数x，问在三个数组中是否存在三个数的和与x相等，此题用for循环来找肯定超时，然后想到先将两个数数组的和算出来，然后利用二分查找

代码：

#include<queue>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    #define max(a,b)a>b?a:b
    #define min(a,b)a>b?b:a
    int a[505],b[505],c[505],d[250005];
    int main()
    {
        int l,m,n,q=1;
        while(scanf("%d%d%d",&l,&m,&n)!=EOF)
        {
            int i,j,ans=0,sum=0,k=0;
            for(i=0; i<l; i++)
                scanf("%d",&a[i]);
            for(i=0; i<m; i++)
                scanf("%d",&b[i]);
            for(i=0; i<n; i++)
                scanf("%d",&c[i]);
            for(i=0; i<l; i++)
            {
                for(j=0; j<m; j++)
                {
                    d[k++]=a[i]+b[j];
                }
            }
            sort(d,d+k);
            int x;
            scanf("%d",&x);
            printf("Case %d:\n",q++);
            while(x--)
            {
                int xx;
                scanf("%d",&xx);
                int flag=0;
                for(i=0; i<n; i++)
                {
                    int tmp=xx-c[i];
                    int left=0;
                    int right=k-1;
                    int mid;
                    while(left<=right)
                    {
                        mid=(left+right)/2;
                        if(d[mid]>tmp)
                        {
                            right=mid-1;
                        }
                        else if(d[mid]<tmp)
                        {
                            left=mid+1;
                        }
                        else
                        {
                            flag=1;
                            break;
                        }
                    }
                    if(d[left]==tmp&&left<k||d[right]==tmp&&right>=0)
                        flag=1;
                    if(flag)
                    {
                        printf("YES\n");
                        break;
                    }
                }
                if(!flag)
                {
                    printf("NO\n");
                }
            }
        }
        return 0;
    }