题意

给定一个绝对值不大于$10^{15}$的$N(N<=35)$个整数列表，找出这些数的一个非空子集，使其元素和的绝对值最小。如果有多个子集，选择元素较少的那个。

Sample Input

1
10
3
20 100 -100
0

Sample Output

10 1
0 2

题解

显然，可以用折半搜索，分别枚举各自一半的选取情况，复杂度为$2×2^{n/2}$。

• 因为集合非空，枚举时考虑只在前一半选、只在后一半选以及两段都选的情况。

• 对于前一半后一半都选的情况，把前一半的结果存下来，排序，枚举后一半的时候在前一半里二分查找最合适的即可。

• 最终答案为只在前一半中选数、只在后一半中选数、在两段都选数的方案三种情况下的最小值。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
#define fi first
#define se second
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<double,int> pdi;
typedef long long LL;
const int INF=0x3f3f3f3f;
const LL IINF=0x3f3f3f3f3f3f3f3f;

const int N=40;
LL a[N];
int n;

LL Abs(LL x)
{
    return x<0?-x:x;
}


int main()
{
    while(~scanf("%d",&n))
    {
        if(!n) break;
        for(int i=0;i<n;i++) cin>>a[i];

        map<LL,int> mp;

        int m=n/2;
        pair<LL,int> ans(IINF,0);

        for(int i=1;i<1<<m;i++)
        {
            LL sum=0;
            int cnt=0;
            for(int j=0;j<m;j++)
                if(i>>j & 1)
                {
                    sum+=a[j];
                    cnt++;
                }
            ans=min(ans,make_pair(Abs(sum),cnt));
            if(mp[sum]) mp[sum]=min(mp[sum],cnt);
            else mp[sum]=cnt;

        }

        m=n-n/2;
        for(int i=1;i<1<<m;i++)
        {
            LL sum=0;
            int cnt=0;
            for(int j=0;j<m;j++)
                if(i>>j & 1)
                {
                    sum+=a[n/2+j];
                    cnt++;
                }

            ans=min(ans,make_pair(Abs(sum),cnt));
            map<LL,int>::iterator it =mp.lower_bound(-sum);// 返回大于或等于-sum的第一个元素位置
            if(it != mp.end())
                ans=min(ans,make_pair(Abs(sum+it->first),cnt+it->second));
            if(it != mp.begin())// 若不存在等于-sun的元素还需比较比该元素小一点点的
            {
                it--;
                ans=min(ans,make_pair(Abs(sum+it->first),cnt+it->second));
            }
        }

        cout<<ans.first<<' '<<ans.second<<endl;
    }
   // system("pause");
}