本文主要是介绍hdu2241（二分+合并数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C
如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了
代码如下（附注释）：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define inf 0x7fffffff
#define eps 1e-9
#define N 505
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int a[N],b[N],c[N],d[N*N];int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);int l,m,n,z = 1;int i,j,k;while(scanf("%d%d%d",&l,&m,&n) != EOF){for(i = 0;i < l; i++)scanf("%d",&a[i]);for(i = 0; i < m; i++)scanf("%d",&b[i]);for(i = 0; i < n; i++)scanf("%d",&c[i]); k = 0; for(i = 0; i < m; i++)//将b,c两个数组和并在d数组内 for(j = 0; j < n; j++)d[k++] = b[i] + c[j];sort(d,d+k);j = 1;for(i = 1; i < k; i++)//对d数组就行优化，去掉相同的数据 if(d[i] != d[i-1])d[j++] = d[i];// for(i = 0; i < j; i++)// cout<<d[i]<<" ";c int t, flag;scanf("%d",&t);printf("Case %d:\n",z++);while(t--){flag = 0; scanf("%d",&k);for(i = 0; i < l; i++){int left = 0,right = j-1;int k1 = k - a[i];// cout<<k<<endl;while(left <= right)//二分查找 {int mid = (left + right)/2;if(d[mid] == k1){printf("YES\n");i = l;flag = 1;break; } if(d[mid] < k1) left = mid + 1;if(d[mid] > k1) right = mid - 1;} } if(!flag) printf("NO\n");}} // P; return 0;
}
这篇关于hdu2241（二分+合并数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
