CSU-ACM2016暑假集训训练1-二分搜索 A - Can you…

2018-06-17 23:58:48来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:bzoj1202 [ HNOI2005 ] --带权并查集+前缀和

下一篇:(转)OpenCV中的常用函数