Poj: 3977-Subset: 清晰题解, 最小化子集和的绝对值, 折半枚举

题目

对于由N个整数组成的序列（N≤35），需要从中挑选出一个子集，使得该子集所有元素之和的绝对值达到最小。若存在多个满足条件的子集，则应优先选择元素数量最少的那个。

思路

观察到问题与数列的和相关，尝试思考是否可以使用尺取法。然而，由于题目并未要求连续数列，因此难以构造一个满足单调性条件的数组以供尺取法使用（如有更好的方法欢迎指正）。进一步思考后，似乎也可以采用二分搜索的方式，将绝对值作为目标值进行处理。不过每个整数可能达到10^{15}级别，且当mid无法作为最小绝对值时，并不意味着mid-1也无法实现。例如，在序列20,-100,100中，虽然10不能成为最小绝对值，但0却可以。因此，在每次判断x是否可以作为最小绝对值时，应采用小于关系进行判断，即是否存在一个序列的和的绝对值小于x。然而，这样做似乎有些多余。如果能够找到一个序列的和的绝对值之和更小，则为何不直接寻找该最小值呢？因此，二分法在此处显得有些多余，实际上只需一次遍历即可求解。

当然，对于数值范围为2^{35}的情况显然无法直接枚举。在面对数据规模过大而无法穷举的问题时，通常需要考虑折半枚举这一方法。针对每一个输入的n而言，我们将数组a[n]划分为两个部分[1,\frac{n}{2}),[\frac{n}{2},n)，

1. 先