题目大意是给定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 = 1000000000000000LL;
int mink = 32;
int l = 0;
int r = (1 << maxm);
for (int i = 0; i < 1 << maxn; i++)
{
l = 0;
int curk = 0;
for (int k = 0; k < maxn; k++)
{
if ((res[0][i].i >> k) & 1)
{
curk++;
}
}
while (r - l > 1)
{
int mid = (l + r) / 2;
long long sum = res[1][mid].res + res[0][i].res;
if (sum > 0)
{
r = mid;
}
else
l = mid;
} l = l >= 1 ? l - 1 : l;
for (int k = l; k < (1 << maxm);k++)
{
int curm = 0;
for (int m = 0; m < maxm; m++)
{
if ((res[1][k].i >> m) & 1)
{
curm++;
}
}
if (curm == 0 && curk == 0)
{
continue;
}
long long sum = res[1][k].res + res[0][i].res;
if (absll(sum) < minvalue)
{
mink = curm + curk;
minvalue = absll(sum);
}
else if (absll(sum) == minvalue)
{
mink = min(mink, curk + curm);
}
else if (sum > 0)
{
break;
}
}
}
printf("%I64d %d\n", minvalue, mink);
}
return 0;
}