题目大意：给定一串数字序列，要你从中挑一定个数的数字使这些数字和绝对值最小，求出最小组合数
题目的数字最多35个，一看就是要数字枚举了，但是如果直接枚举，复杂度就是O(2^35)了，显然行不通，所以我们把它的组合拆成两半（前n/2个数字和后n-n/2个数字），然后给前部分和或者后部分和的组合排序，然后再用另一半在其二分查找，看最接近的和，这就是折半枚举的思想
不过这一题有很多细节：
1.和是不固定的，要左右各查找1个，如果有重复元素，一定要越过重复元素再找(lower_bound和upper_bound找就好了)，同时还要防止空子列
2.这一题要找的数组合数最小的和个组合，所以排序的那一个组合，当两个组合的和一样时，要按照nums的升序排列，这样也会让1的查找顺利
#include <iostream>
#include <algorithm>
#include <functional> using namespace std; typedef long long LL_INT;
static struct _set
{
int nums;
LL_INT sum;
bool operator <(const _set&x) const
{
if (sum != x.sum)
return sum < x.sum;
else
return nums < x.nums;//如果相等则按nums排序，那样只用看upper_bound就可以了
}
}sum_set1[], sum_set2[];
static LL_INT input[];
static int search_bound[] = { -, }; LL_INT ABS(LL_INT);
int Min(const int, const int);
void Solve(const int, LL_INT &, int &);
struct _set *Binary_Search_Lower(const int, LL_INT);
struct _set *Binary_Search_Upper(const int, LL_INT); int main(void)
{
int ans2, n;
LL_INT ans1; while (~scanf("%d",&n))
{
if (n == )break;
for (int i = ; i < n; i++)
scanf("%lld", &input[i]); for (int i = ; i < << (n / ); i++)//枚举左半边元素
{
sum_set1[i].nums = ; sum_set1[i].sum = ;
for (int pos = ; pos < n / ; pos++)
{
if (((i >> pos) & ) == )
{
sum_set1[i].sum += input[pos];
sum_set1[i].nums++;
}
}
}
for (int i = ; i < <<(n - (n / )); i++)//枚举右半边元素
{
sum_set2[i].nums = ; sum_set2[i].sum = ;
for (int pos = ; pos < (n - (n / )); pos++)
{
if (((i >> pos) & ) == )
{
sum_set2[i].sum += input[pos + n / ];
sum_set2[i].nums++;
}
}
}
sort(sum_set2, sum_set2 + ( << (n - (n / ))));
Solve(n, ans1, ans2);
printf("%lld %d\n", ans1, ans2);
}
return EXIT_SUCCESS;
} LL_INT ABS(LL_INT x)
{
return x > ? x : -x;
} int Min(const int x, const int y)
{
return x > y ? y : x;
} void Solve(const int n, LL_INT &ans1, int &ans2)
{
struct _set *pos = NULL, *pos_up = NULL;
int tmp_pos, up;
ans1 = LLONG_MAX; ans2 = -; for (int i = ; i < << (n / ); i++)
{
pos = Binary_Search_Lower( << (n - (n / )), -sum_set1[i].sum);
pos_up = Binary_Search_Upper( << (n - (n / )), -sum_set1[i].sum);
//一定要记得在找到的范围附近再寻找看还有没有绝对值更接近的
for (int j = ; j < ; j++)
{
tmp_pos = (int)(pos - sum_set2) + search_bound[j];
if ( <= tmp_pos && tmp_pos < << (n - (n / ))
&& (sum_set2[tmp_pos].nums || i)//不同时为0（避免空子串）
)
{
if (ABS(sum_set2[tmp_pos].sum + sum_set1[i].sum) < ans1)
{
ans1 = ABS(sum_set2[tmp_pos].sum + sum_set1[i].sum);
ans2 = sum_set2[tmp_pos].nums + sum_set1[i].nums;
}
else if (ABS(sum_set2[tmp_pos].sum + sum_set1[i].sum) == ans1)
ans2 = Min(sum_set2[tmp_pos].nums + sum_set1[i].nums, ans2);
}
}
up = (int)(pos - sum_set2) + ;
if (sum_set2[up].nums || i)//避免空子串,导致后面失效
{
if (ABS(sum_set2[up].sum + sum_set1[i].sum) < ans1)
{
ans1 = ABS(sum_set2[up].sum + sum_set1[i].sum);
ans2 = sum_set2[up].nums + sum_set1[i].nums;
}
else if (ABS(sum_set2[up].sum + sum_set1[i].sum) == ans1)
ans2 = Min(sum_set2[up].nums + sum_set1[i].nums, ans2);
}
up = (int)(pos_up - sum_set2);
if (sum_set2[up].nums || i)//不同时为0（避免空子串）
{
if (ABS(sum_set2[up].sum + sum_set1[i].sum) < ans1)
{
ans1 = ABS(sum_set2[up].sum + sum_set1[i].sum);
ans2 = sum_set2[up].nums + sum_set1[i].nums;
}
else if (ABS(sum_set2[up].sum + sum_set1[i].sum) == ans1)
ans2 = Min(sum_set2[up].nums + sum_set1[i].nums, ans2);
}
}
} struct _set *Binary_Search_Lower(const int n, LL_INT sum1)
{
int lb = , mid, count1 = n, count2;
while (count1 > )
{
count2 = count1 >> ;
mid = lb + (count1 >> );
if (sum_set2[mid].sum < sum1)
{
lb = ++mid;
count1 -= count2 + ;
}
else count1 = count2;
}
return &sum_set2[lb];
} struct _set *Binary_Search_Upper(const int n, LL_INT sum1)
{
int lb = , mid, count1 = n, count2;
while (count1 > )
{
count2 = count1 >> ;
mid = lb + (count1 >> );
if (sum_set2[mid].sum <= sum1)
{
lb = ++mid;
count1 -= count2 + ;
}
else count1 = count2;
}
return &sum_set2[lb];
}
最后尼玛，我wa很多次，发现原来是我的min函数写错了。。。写成了max函数。。。。。
参考了一下http://www.cnblogs.com/hyxsolitude/p/3642053.html