题目描述
A、B、C三个数组,使得各三者中每一元素之和为X;
先把A、B两个数组中的元素相加,得到D数组。
再用X分别减去C中元素,并分别二分。
模板一和二都可以。
可以把复杂度降低为O( (2nlog(n) )。
做过两个的数组之和得X的题,所以这道题应该也可以用类似于双指针的方法,等有空写一下。
C++ 代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const int N=1e3+10;
LL a[N],b[N],c[N],d[N*N],x[N];
int BinarySearch(int k,int target)
{
int L,R,mid=0;
L=0;
R=k-1;
while(L<R)
{
mid=(L+R)>>1;
if(d[mid]>=target) R=mid;
else L=mid+1;
}
if(target==d[R]) return R;
return -1;
}
int main()
{
int l,m,n,s;
int cnt=0;
while(scanf("%d%d%d",&l,&m,&n)!=EOF)
{
for(int i=0;i<l;i++)
{
scanf("%lld",&a[i]);
}
for(int i=0;i<m;i++)
{
scanf("%lld",&b[i]);
}
for(int i=0;i<n;i++)
{
scanf("%lld",&c[i]);
}
int k=0;
for(int i=0;i<l;i++)
{
for(int j=0;j<m;j++)
{
d[k++]=a[i]+b[j];
}
}
sort(d,d+k);
sort(c,c+n);
printf("Case %d:\n",++cnt);
scanf("%d",&s);
while(s--)
{
int q;
scanf("%d",&q);
int flag=0;
if(q<d[0]+c[0]||q>d[k-1]+c[n-1])
{
printf("NO\n");
continue;
}
for(int j=0;j<n;j++)
{
if(BinarySearch(k,q-c[j])!=-1)
{
printf("YES\n");
flag=1;
break;
}
}
if(!flag)printf("NO\n");
}
}
return 0;
}