现在的位置: 首页 > 综合 > 正文

hdu 2141 Can you find it? 二分

2012年11月11日 ⁄ 综合 ⁄ 共 1104字 ⁄ 字号 评论关闭

 

/*
* hdu2141.c
*
* Created on: 2011-10-9
* Author: bjfuwangzhu
*/

#include<stdio.h>
#include<stdlib.h>
#define nmax 5001
#define nnum 250001
#define LL long long
LL numL[nmax], numN[nmax], numM[nmax], numLN[nnum];
int cmp(const void *a, const void *b) {
LL temp = *(LL *) a - *(LL *) b;
if (temp > 0) {
return 1;
} else if (temp < 0) {
return -1;
}
return 0;
}
int Mbsearch(LL key, int n) {
int left, right, mid;
left = 0, right = n;
while (left <= right) {
mid = (left + right) >> 1;
if (numLN[mid] == key) {
return 1;
} else if (numLN[mid] > key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return 0;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int L, N, M, S, i, j, k, cas;
LL X;
cas = 0;
while (~scanf("%d %d %d", &L, &N, &M)) {
for (i = 0; i < L; i++) {
scanf("%I64d", numL + i);
}
for (i = 0; i < N; i++) {
scanf("%I64d", numN + i);
}
for (i = 0; i < M; i++) {
scanf("%I64d", numM + i);
}
for (i = 0, k = 0; i < L; i++) {
for (j = 0; j < N; j++) {
numLN[k++] = numL[i] + numN[j];
}
}
qsort(numLN, k, sizeof(numLN[0]), cmp);
qsort(numM, M, sizeof(numM[0]), cmp);
scanf("%d", &S);
printf("Case %d:\n", ++cas);
for (i = 0; i < S; i++) {
scanf("%I64d", &X);
if (X < numLN[0] + numM[0] || X > numLN[k - 1] + numM[M - 1]) {
puts("NO");
} else {
for (j = 0; j < M; j++) {
if (Mbsearch(X - numM[j], k)) {
puts("YES");
break;
}
}
if (j == M) {
puts("NO");
}
}
}

}
return 0;
}

抱歉!评论已关闭.