POJ 3977 Subset 题解 《挑战程序设计竞赛》

POJ 3977 Subset

子集：从N个数中挑出非空子集使得和的绝对值最小。

3.2常用技巧精选（一）

折半枚举

子集最多有(2^N)2³⁵个，根本枚举不过来。所以折半先枚举前半，记录和及个数。在枚举后半时，使用二分法查找与相反数最相近的那一个和，在那附近就有答案。这道题用map非常方便，不过POJ似乎在使用我不熟悉的编译器：

• Compile Error

Main.cpp
F:\temp\12899831.949\Main.cpp(26) : error C2668: 'abs' : ambiguous call to overloaded function
        math.h(539): could be 'long double abs(long double)'
        math.h(491): or       'float abs(float)'
        math.h(487): or       'double abs(double)'
        math.h(485): or       'long abs(long)'
        stdlib.h(380): or       'int abs(int)'
        while trying to match the argument list '(LL)'
F:\temp\12899831.949\Main.cpp(52) : error C2668: 'abs' : ambiguous call to overloaded function
        math.h(539): could be 'long double abs(long double)'
        math.h(491): or       'float abs(float)'
        math.h(487): or       'double abs(double)'
        math.h(485): or       'long abs(long)'
        stdlib.h(380): or       'int abs(int)'
        while trying to match the argument list '(LL)'
F:\temp\12899831.949\Main.cpp(52) : error C2780: 'const _Ty &std::min(const _Ty &,const _Ty &,_Pr)' : expects 3 arguments - 2 provided
        xutility(3379) : see declaration of 'std::min'
F:\temp\12899831.949\Main.cpp(85) : error C2668: 'abs' : ambiguous call to overloaded function
        math.h(539): could be 'long double abs(long double)'
        math.h(491): or       'float abs(float)'
        math.h(487): or       'double abs(double)'
        math.h(485): or       'long abs(long)'
        stdlib.h(380): or       'int abs(int)'
        while trying to match the argument list '(LL)'
F:\temp\12899831.949\Main.cpp(85) : error C2780: 'const _Ty &std::min(const _Ty &,const _Ty &,_Pr)' : expects 3 arguments - 2 provided
        xutility(3379) : see declaration of 'std::min'

干脆自己写个abs糊弄过去了(￣▽￣") ：

#include <iostream>
#include <algorithm>
#include <limits>
#include <map>
using namespace std;
typedef long long LL;
#define MAX_N 36
LL number[MAX_N];

LL ll_abs(const LL& x)	// damn it! error C3861: 'llabs': identifier not found
{
	return x >= 0 ? x : -x;
}

///////////////////////////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 >> number[i];
		}
		map<LL, int> dp;	// sum的值<->集合元素个数，这里不是绝对值
		pair<LL, int> result(ll_abs(number[0]), 1);	// 最优解
		for (int i = 0; i < 1 << (N / 2); ++i)	// 枚举前 N / 2
		{
			LL sum = 0;
			int num = 0;
			for (int j = 0; j < N / 2; ++j)
			{
				if ((i >> j) & 1)
				{
					sum += number[j];
					++num;
				}
			}
			if (num == 0)
			{
				continue;
			}
			result = min(result, make_pair(ll_abs(sum), num));
			map<LL, int>::iterator it = dp.find(sum);
			if (it != dp.end())
			{
				it->second = min(it->second, num);
			}
			else
			{
				dp[sum] = num;
			}
		}

		for (int i = 0; i < 1 << (N - N / 2); ++i)	// 枚举剩下的
		{
			LL sum = 0;
			int num = 0;
			for (int j = 0; j < N - N / 2; ++j)
			{
				if ((i >> j) & 1)
				{
					sum += number[N / 2 + j];
					++num;
				}
			}
			if (num == 0)
			{
				continue;
			}
			result = min(result, make_pair(ll_abs(sum), num));
			// 找寻跟-sum最相近的结果
			map<LL, int>::iterator it = dp.lower_bound(-sum);	// 返回大于或等于-sum的第一个元素位置
			if (it != dp.end())
			{// 可能是该位置
				result = min(result, make_pair(ll_abs(sum + it->first), num + it->second));
			}
			if (it != dp.begin())
			{// 或比该元素小一点点的
				--it;
				result = min(result, make_pair(ll_abs(sum + it->first), num + it->second));
			}
		}
		cout << ll_abs(result.first) << ' ' << result.second << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

15秒，长见识了。

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