HDU-2141

2019-11-09 21:06:50

字體：大中小

供稿：網(wǎng)友

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. InputThere 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. OutputFor 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 331410Sample OutputCase 1:NOYESNO這道題就是首先想到會將他們?nèi)齻€數(shù)表的所有情況列出來，放進一個數(shù)組里，但是這樣去做的時候，就會超出限制，也就是會出現(xiàn)memory limited exceed，再去看題目的要求，發(fā)現(xiàn)這里的每一個數(shù)表的大小是500，三個數(shù)表的大小相乘。就會超過10000kb的限制，但是如果是兩個數(shù)表的大小乘起來的話，就不會超過限制，所以可以想到，先將兩個數(shù)表的和算出來，然后再根據(jù)答案，在剩下的一個數(shù)表中用二分法找答案，由于二分法是需要數(shù)表有序的，就可以用頭文件algorithm中的sort，當然這就是具體的解體細節(jié)了，然后將思路實現(xiàn)這樣就可以ac了#include<iostream>#include<algorithm>using namespace std;int find_need(int a[],int s,int need){    int low = 0;    int high = s-1;    while(low<high)    {        int mid = (low+high)/2;        if(a[low]==need||a[high]==need||a[mid]==need) return true;        else if(a[mid]>need) high = mid-1;        else low = mid+1;    }    return false;}int main(){    int times = 0;    int anum,bnum,cnum;    while(cin>>anum>>bnum>>cnum)    {        times++;        cout<<"Case "<<times<<":"<<endl;        int ava[anum],bva[bnum],cva[cnum];        for(int i = 0;i<anum;i++)            cin>>ava[i];        for(int i = 0;i<bnum;i++)            cin>>bva[i];        for(int i = 0;i<cnum;i++)            cin>>cva[i];        int sum[bnum*cnum];        int help = 0;        for(int i = 0;i<bnum;i++)        {            for(int j = 0;j<cnum;j++)            {                sum[help] = bva[i]+cva[j];                help++;            }        }        sort(sum,sum+bnum*cnum);        int xnum;        cin>>xnum;        int yes[xnum];        int xva[xnum];        for(int i = 0;i<xnum;i++)        {            yes[i] = 0;            cin>>xva[i];            for(int j = 0;j<anum;j++)            {                if(find_need(sum,bnum*cnum,xva[i]-ava[j]))                {                    yes[i] = 1;                    break;                }            }            if(yes[i]==1) cout<<"YES"<<endl;            else cout<<"NO"<<endl;        }    }}