CSU-ACM2016暑假集訓訓練1-二分搜索 A，csu-acm20161-

CSU-ACM2016暑假集訓訓練1-二分搜索 A，csu-acm20161-

Time Limit:3000MS     Memory Limit:10000KB     64bit IO Format:%I64d & %I64u

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 3 1 2 3 1 2 3 1 2 3 3 1 4 10  

Sample Output

Case 1: NO YES NO   解題思路：題目大意：給出3串整數A,B,C及整數X，如果存在一組數Ai,Bj,Ck，使得Ai+Bj+Ck=X成立，則輸出“YES”，否則輸出“NO”。 數據類型使用int即可。首先看到題目想到的是暴力法破解，3個for循環，時間復雜度為O(n3)。當n達到一定規模時此方法不可取。還容易想到二分檢索，效率比較高。思路：對後兩個序列求和，結果排序去重。時間復雜度為O(n2)。對第一個序列枚舉，二分檢索和序列，時間為nlgn。因此總的時間復雜度為O(n2，方案可行。   收獲感想：由於昨天上課學習到二分查找的應用，還比較熟悉，其中數組去重浪費了一點時間，由於保存兩個數組的和時創建了一個新的數組，如果在創建一個數組來保存去重以後的結果就沒有必要了，直接利用原來的數組，由於有序，只要比較前後兩個數，從第一個數開始，計數器第一次出現的位置，再往後遍歷，直到新的數出現，將其往前移，覆蓋掉重復的值，計數器加1。        

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int A[501],B[501],C[501],temp[250001];
    int L,N,M,S,i;int d=1;
    while(cin>>L>>N>>M)
    {


        if(L<1||L>500||N<1||N>500||M<1||M>500) return -1;
        //輸入
        for(i=0;i<L;i++) cin>>A[i];
        for(i=0;i<N;i++) cin>>B[i];
        for(i=0;i<M;i++) cin>>C[i];
        cin>>S;
        if(S<1||S>1000) return -1;

        //求後兩組的和保存到temp中
        int tp=0;
        for(i=0;i<N;i++)
        for(int t=0;t<M;t++)
        {
            temp[tp]=B[i]+C[t];
            tp++;
        }
        sort(temp,temp+M*N);
        //數組去重
        int tp1=0;
        for(i=1;i<M*N;i++)
        {
            if(temp[i]==temp[i-1]) continue;
            else {tp1++;temp[tp1]=temp[i];}
        }

        cout<<"Case "<<d<<":"<<endl;
        while(S--){
            int flag=1;
            int X;
            cin>>X;
            for(i=0;i<L;i++){
            int lo=0,hi=tp1;
            int mi;
        while(lo<=hi)
      {
        mi=((hi-lo)>>1)+lo;//lo和hi比較大的時候相加可能爆int
        if((A[i]+temp[mi])==X) {flag=0; break;}
        else if(A[i]+temp[mi]<X) lo=mi+1;
        else hi=mi-1;
      }
            }
      if(!flag) cout<<"YES"<<endl;
      else cout<<"NO"<<endl;

        }
       d++;
}
    return 0;
}