HDU OJ 2141

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2141

解题的关键在于把判断a + b + c = x转化为a + b = x - c，算出a + b的所有组合，然后快排，二分搜索。

做了个优化，把c也排序，这样能在搜索中不断减少搜索空间，但似乎没快多少。以下代码

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

//#define TEST

int a_array[500];
int a_array_len;

int b_array[500];
int b_array_len;

int c_array[500];
int c_array_len;

long long d_array[500];
int d_array_len;

long long sum_array[250000];
int sum_array_len;

int cmp(const void *a, const void *b)
{
    long long s = *(int *)a - *(int *)b;
    if (s > 0) return 1;
    if (s == 0) return 0;
    if (s < 0) return -1;
}

int cmpc(const void *a, const void *b)
{
    long long s = *(int *)b - *(int *)a;
    if (s > 0) return 1;
    if (s == 0) return 0;
    if (s < 0) return -1;
}

void Prepare()
{
    sum_array_len = 0;

    for (int i=0; i<a_array_len; ++i) {
	for (int j=0; j<b_array_len; ++j) {
	    sum_array[sum_array_len++] = a_array[i] + b_array[j];
	}
    }

#ifdef TEST

    printf("test log:\n");
    for (int i=0; i<sum_array_len; ++i) cout << sum_array[i] << ", ";
    printf("\n");

#endif

    qsort(sum_array, sum_array_len, sizeof(sum_array[0]), cmp);
    qsort(c_array, c_array_len, sizeof(c_array[0]), cmpc);
#ifdef TEST

    printf("test log:\n");
    for (int i=0; i<sum_array_len; ++i) cout << sum_array[i] << ", ";
    printf("\n");
    for (int i=0; i<c_array_len; ++i) printf("%d, ", c_array[i]);
    printf("\n");

#endif

}

bool Judge(const int &x)
{
    for (int i=0; i<c_array_len; ++i) {
	d_array[i] = x - c_array[i];
    }

    int low = 0;
    int high = sum_array_len - 1;
    int center;

    for (int i=0; i<d_array_len; ++i) {
	while (high >= low) {
	    center = (low + high) / 2;
	    if (sum_array[center] == d_array[i]) return true;
	    if (sum_array[center] > d_array[i]) {
		high = center - 1;
	    } else {
		low = center + 1;
	    }
	}

	low = center;
	high = sum_array_len - 1;
    }

    return false;
}

int MaxInArray(int array[], const int &len)
{
    int max = array[0];

    for (int i=1; i<len; ++i) {
	if (array[i] > max) max = array[i];
    }

    return max;
}

int MinInArray(int array[], const int &len)
{
    int min = array[0];

    for (int i=1; i<len; ++i) {
	if (array[i] < min) min = array[i];
    }

    return min;
}

inline void Yes()
{
    printf("YES\n");
}

inline void No()
{
    printf("NO\n");
}

int main()
{
    int case_count = 0;

    while (scanf("%d%d%d", &a_array_len, &b_array_len, &c_array_len) != EOF) {
	printf("Case %d:\n", ++case_count);
	d_array_len = c_array_len;

	for (int i=0; i<a_array_len; ++i) {
	    scanf("%d", a_array + i);
	}

	for (int i=0; i<b_array_len; ++i) {
	    scanf("%d", b_array + i);
	}

	for (int i=0; i<c_array_len; ++i) {
	    scanf("%d", c_array + i);
	}

	int x_count;
	scanf("%d", &x_count);
	/*bool prepared = false;
	long long max_sum = MaxInArray(a_array, a_array_len) + MaxInArray(b_array, b_array_len)
		    + MaxInArray(c_array, c_array_len);
	long long min_sum = MinInArray(a_array, a_array_len) + MinInArray(b_array, b_array_len)
		           + MinInArray(c_array, c_array_len);*/
	Prepare();
	for (int i=0; i<x_count; ++i) {
	    int x;
	    scanf("%d", &x);
	    /*if (x > max_sum) {
		No();
		continue;
	    } else if (x < min_sum) {
		No();
		continue;
	    }
	    if (!prepared) {
		Prepare();
		prepared = true;
	    }*/
	    bool result = Judge(x);
	    if (result) {
		Yes();
	    } else {
		No();
	    }
	}
    }

    return 0;
}

注释部分是在我看来“显然正确”的剪枝，但是WA了，不明白为什么，留此存疑。

可恶的是Judge函数一度忘了写return false，浪费了不少时间，而GCC竟然不报warning！不知道在命令行下怎么提高它的警告级别，愿知者以闻。