【二分】HDU 2141 Can you find it?_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 【二分】HDU 2141 Can you find it?

【二分】HDU 2141 Can you find it?

 2011/12/8 8:11:54  基德KID.1412  http://972169909-qq-com.iteye.com  我要评论(0)
  • 摘要:KIDx的解题报告题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2141题意很简单很好的一道二分+降维思想的题!#include<iostream>#include<algorithm>usingnamespacestd;#defineeps1e-8#definePI3.14159265#definePOW2(x)x*x#definePOW3(x)x*x*x#definePOW4(x)x*x*x*xinta[505]
  • 标签:can
KIDx 的解题报告
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2141

题意很简单
很好的一道二分+降维思想的题!

#include <iostream>
#include <algorithm>
using namespace std;
#define eps 1e-8
#define PI 3.14159265
#define POW2(x) x*x
#define POW3(x) x*x*x
#define POW4(x) x*x*x*x

int a[505], b[505], c[505], bc[250005];

int main()
{
	int L, N, M, i, j, S, x, cc = 1, l, r, mid, k;
	while (~scanf ("%d%d%d", &L, &N, &M))
	{
		k = 0;
		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 (i = 0; i < N; i++)
			for (j = 0; j < M; j++)
				bc[k++] = b[i] + c[j];
		sort (bc, bc+k);
		scanf ("%d", &S);
		printf ("Case %d:\n", cc++);
		while (S--)
		{
			scanf ("%d", &x);
			for (i = 0; i < L; i++)
			{
				int tp = x - a[i];
				l = 0, r = k - 1;
				while (l < r)
				{
					mid = (l+r) / 2;
					if (bc[mid] == tp)
					{
						puts ("YES");
						goto end;
					}
					else if (bc[mid] > tp)
						r = mid;
					else l = mid + 1;
				}
			}
			puts ("NO");
end:;
		}
	}
    return 0;
}
发表评论
用户名: 匿名