注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

HDU 2141 Can you find it? 两个数组和为一个的二分  

2014-04-28 21:55:32|  分类: 搜索的入门 二分 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

#include<stdio.h>/*把两组数据合并在一起的思想值得我们去学习,很难想啊,wawa了十多次啊*/
#include<algorithm>
using namespace std;

int a[505],b[505],c[505];
long long d[250005];

bool binarysearch(int x,int q,int p)
{
int bottom=q;
int top=p;
int mid;
while(bottom<=top)
{
mid=(bottom+top)/2;
if(d[mid]==x)
{
return true;
}
else if(d[mid]>x)
{
top=mid-1;
}
else
{
bottom=mid+1;
}
}

return false;
}
int main()
{
int l,n,m;
int i,j,k;
int sum;
int s;
int count=1 ;
int flag;
while(scanf("%d%d%d",&l,&n,&m)!=EOF)
{
for(i=0;i<l;i++)
{
scanf("%d",&a[i]) ;
}
for(i=0;i<n;i++)
{
scanf("%d",&b[i]) ;
}
for(i=0;i<m;i++)
{
scanf("%d",&c[i]) ;
}
for(k=0,i=0;i<l;i++)
{
for(j=0;j<n;j++)
{
d[k++]=a[i]+b[j];
}
}
sort(d,d+k);
printf("Case %d:\n",count++);
scanf("%d",&s);
for(i=0;i<s;i++)
{
flag=1;
scanf("%d",&sum);
for(j=0;j<m;j++)
{
if(binarysearch(sum-c[j],0,k-1))/*明显的我差 d的数据比c的大 怎么去二分c呢!!!!!!!!!!!!*/
{
flag=0;
break;
}

}
if(flag==1)
{
printf("NO\n");
}
else
{
printf("YES\n");
}
}
}
return 0;
}


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

 


Sample Output

Case 1:
NO
YES
NO

 


Author

wangye

 


Source

HDU 2007-11 Programming Contest

 




  评论这张
 
阅读(10)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017