题目大意是给定N个数的集合，从这个集合中找到一个非空子集，使得该子集元素和的绝对值最小，如果有多个答案，输出元素个数最少的那个。   

N最多为35，如果直接枚举显然是不行的。但是如果我们将这些数分成两半后再枚举的话，最多有2^18(262144)，此时我们两半枚举后的结果进行排序后再二分搜索一下就可以了。复杂度为O(nlogn) n最多2^18。

#include <stdio.h>
#include <vector>
#include <math.h>
#include <string.h>
#include <string>
#include <iostream>
#include <queue>
#include <list>
#include <algorithm>
#include <stack>
#include <map>

using namespace std;

struct MyStruct
{
	long long res;
	int i;
};

int compp(const void* a1, const void* a2)
{
	long long dif = ((MyStruct*)a1)->res - ((MyStruct*)a2)->res;
	if (dif > 0)
	{
		return 1;
	}
	else if (dif == 0)
	{
		return 0;
	}
	else
		return -1;
}

MyStruct res[2][300000];

inline long long absll(long long X)
{
	if (X < 0)
	{
		return X * (-1);
	}
	else
		return X;
}

int main()
{
	int n;
#ifdef _DEBUG
	freopen("d:\\in.txt", "r", stdin);
#endif
	long long values[36];
	while (scanf("%d", &n) != EOF)
	{
		if (n == 0)
		{
			break;
		}
		for (int i = 0; i < n; i++)
		{
			scanf("%I64d", &values[i]);
		}
		int maxn = n - n / 2;
		int maxm = n - maxn;
		memset(res, 0, sizeof(res));
		for (int i = 0; i < 1 << maxn; i++)
		{
			res[0][i].i = i;
			for (int k = 0; k < 19; k++)
			{
				if ((i >> k) & 1)
				{
					res[0][i].res += values[k];
				}
			}
		}
		qsort(res[0], 1 << maxn, sizeof(MyStruct), compp);
		for (int i = 0; i < 1 << maxm; i++)
		{
			res[1][i].i = i;
			for (int k = 0; k < 19; k++)
			{
				if ((i >> k) & 1)
				{
					res[1][i].res += values[k + maxn];
				}
			}
		}
		qsort(res[1], 1 << maxm, sizeof(MyStruct), compp);
		long long minvalue = http://www.mamicode.com/1000000000000000LL;>

POJ3977 Subset 折半枚举