POJ 2549 Sumsets 题解 《挑战程序设计竞赛》

POJ 2549 Sumsets

子集：从S中找出子集{a,b,c,d}使得 a + b + c = d且d最大。

3.2常用技巧精选（一）

折半枚举

睡不着，A一题提提神。子集最多有1000C4*4个，时限只有一秒。折半枚举有些讲究，以前折半都是在集合上折半，这次是在等式上。将等式变化为 a + b = d – c，预先算好左右两边并排序。左边全枚举N²，右边二分查找logN²，每枚举一次左边都会在右边二分常数次，所以总的复杂度是O(N²logN²)：

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
#define MAX_N 1000 + 16
typedef long long LL;
struct Half
{
	LL v;
	int i, j;
	Half(LL v, int i, int j) : v(v), i(i), j(j){}
	bool operator < (const Half& other) const
	{
		return v < other.v;
	}
	bool operator > (const Half& other) const
	{
		return v > other.v;
	}
	bool operator != (const Half& other) const
	{
		return i != other.i && j != other.j && i != other.j && j != other.i;
	}
};
LL S[MAX_N];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n;
	while (cin >> n && n)
	{
		for (int i = 0; i < n; ++i)
		{
			cin >> S[i];
		}
		vector<Half> left, right;
		for (int i = 0; i < n; ++i)
		{
			for (int j = i + 1; j < n; ++j)
			{
				left.push_back(Half(S[i] + S[j], i, j));
			}
		}

		for (int i = 0; i < n; ++i)
		{
			for (int j = i + 1; j < n; ++j)
			{
				right.push_back(Half(S[i] - S[j], i, j));
				right.push_back(Half(S[j] - S[i], j, i));
			}
		}

		sort(left.begin(), left.end(), greater<Half>());
		sort(right.begin(), right.end());
		LL result; memset(&result, 0x80, sizeof(LL));
		for (vector<Half>::const_iterator it = left.begin(); it != left.end(); ++it)
		{
			vector<Half>::iterator lb = lower_bound(right.begin(), right.end(), *it);
			vector<Half>::iterator ub = upper_bound(lb, right.end(), *it);
			for (; lb != ub; ++lb)
			{
				if (*lb != *it)
				{
					result = max(result, it->v + S[lb->j]);
				}
			}
		}
		if (result < -536870912)
		{
			cout << "no solution" << endl;
		}
		else
		{
			cout << result << endl;
		}
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2549 Sumsets 题解 《挑战程序设计竞赛》