hdu 2141(二分）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2141

最近想做做水题找找感觉。。orz,水题也不好切啊。。。一开始没分析，直接暴力，可想而知，TLE。。。然后就用了二分。。。wa了好几次。。

View Code

 1 #include<iostream>
 2 #include<algorithm>
 3 const int MAXN=507;
 4 using namespace std;
 5 __int64  a[MAXN],b[MAXN],c[MAXN],d[MAXN*MAXN];
 6 
 7 int Binary_Search(__int64 number,int low,int high){
 8     while(low<=high){
 9         int mid=(low+high)/2;
10         if(d[mid]==number)return 1;
11         else if(d[mid]>number)high=mid-1;
12         else low=mid+1;
13     }
14     return 0;
15 }
16 
17 
18 int main(){
19     int L,N,M;
20     int _case=1;
21     while(~scanf("%d%d%d",&L,&N,&M)){
22         for(int i=0;i<L;i++)scanf("%I64d",&a[i]);
23         for(int i=0;i<N;i++)scanf("%I64d",&b[i]);
24         for(int i=0;i<M;i++)scanf("%I64d",&c[i]);
25         int l=0;
26         for(int i=0;i<L;i++){
27             for(int j=0;j<N;j++){
28                 d[l++]=a[i]+b[j];
29             }
30         }
31         sort(c,c+M);
32         sort(d,d+l);
33         int s;
34         scanf("%d",&s);
35         printf("Case %d:\n",_case++);
36         while(s--){
37             __int64 x;
38             scanf("%I64d",&x);
39             if(x<c[0]+d[0]||x>c[M-1]+d[l-1]){
40                 printf("NO\n");
41                 continue;
42             }
43             int flag=0;
44             for(int i=0;i<M;i++){
45                 __int64 tmp=x-c[i];
46                 if(Binary_Search(tmp,0,l-1)){
47                     flag=1;
48                     break;
49                 }
50             }
51             if(flag){
52                 printf("YES\n");
53             }else 
54                 printf("NO\n");
55         }
56     }
57     return 0;
58 }
59 
60 
61             
62