hdu Can you find it

时间:2023-03-09 02:48:04
hdu Can you find it

这道题也是道二分的题,主要有几个注意点:

1、两个数组的合并的问题,可以将a数组和b数组合并,这样可以降低时间复杂度。

2、二分查找的left和right的变化问题。之前这里一直wa。。。一定要是left=mid+1,right=mid-1;可以测试一下x=3和x=9以及x=10这个特殊的值。

剩下的就是二分查找的问题了。

#include"iostream"
#include"stdio.h"
#include"algorithm"
#include"string.h"
#include"cmath"
#define mx 505
using namespace std;
int l,m,n,s,h;
int a[mx],b[mx],c[mx],ab[mx*mx],x; bool test(int xx)
{
int left=;
int right=h-;
while(left<=right)
{
int mid=(right+left)/;
if(ab[mid]==xx) return true;
else if(ab[mid]>xx) right=mid-;
else left=mid+;
}
return false;
} int main()
{
int i,j,k,p;
int count=;
while(scanf("%d%d%d",&l,&m,&n)==)
{
count++;
for(i=;i<l;i++) cin>>a[i];
for(j=;j<m;j++) cin>>b[j];
for(k=;k<n;k++) cin>>c[k];
h=;
for(i=;i<l;i++)
for(j=;j<m;j++)
{
ab[h++]=a[i]+b[j];//合并a和b
}
sort(c,c+n);sort(ab,ab+h);
cout<<"Case "<<count<<":"<<endl;
cin>>s;
for(p=;p<s;p++){
cin>>x;
int flag=;
for(i=;i<n;i++)
{
int a=x-c[i];
if(test(a)) {flag=;break;}
}
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
return ;
}