Subset(折半枚举+二分查找)

题意：

给定个数，要求找到一个子集，使得子集内所有数绝对值之和最小，当有不同子集都最小时，输入子集大小最小者。输入最小的和和子集的大小（）

题解：

观察到，如果对这个数都进行枚举，当较大时就会超时，但是考虑到折半枚举，分成和两部分，最高是次，是可以接受的。因此可以对前算出每种情况的绝对值之和，同时记录每种情况的和和数量。在枚举后时，只需要同前一样算出每种情况和的同时，在算出每种情况的和的相反数与前最相近的前后结果，更新最小值即可，这个寻找最接近的数可以通过二分查找来实现。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define mp make_pair
typedef long long ll;
ll a[40];

int main()
{
    int n;
    while (scanf("%d", &n) != EOF && n)
    {
        for (int i = 0; i < n; i++)
            scanf("%lld", &a[i]);
        pair<ll, ll> ans = mp(abs(a[0]), 1);
        map<ll, ll> m;
        int n1 = n >> 1, n2 = n - (n >> 1);
        for (int i = 1; i < (1 << n1); i++)
        {
            ll sum = 0, cnt = 0;
            for (int j = 0; j < n1; j++)
                if ((i >> j) & 1)
                    sum += a[j], cnt++;
            ll sum1 = abs(sum);
            if (sum1 < ans.first || (sum1 == ans.first && cnt < ans.second))
                ans = mp(sum1, cnt);
            if (m[sum])
                m[sum] = min(m[sum], cnt);
            else
                m[sum] = cnt;
        }
        for (int i = 1; i < (1 << n2); i++)
        {
            ll sum = 0, cnt = 0;
            for (int j = 0; j < n2; j++)
            {
                if ((i >> j) & 1)
                    sum += a[j + n1], cnt++;
            }
            ll sum1 = abs(sum);
            if (sum1 < ans.first || (sum1 == ans.first && cnt < ans.second))
                ans = mp(sum1, cnt);
            map<ll, ll>::iterator it = m.lower_bound(-sum);
            if (it != m.end())
            {
                ll s = abs(it->first + sum), t = it->second + cnt;
                if (s < ans.first || (s == ans.first && t < ans.second))
                    ans = mp(s, t);
            }
            if (it != m.begin())
            {
                it--;
                ll s = abs(it->first + sum), t = it->second + cnt;
                if (s < ans.first || (s == ans.first && t < ans.second))
                    ans = mp(s, t);
            }
        }
        printf("%lld %lld\n", ans.first, ans.second);
    }
    return 0;
}