POJ3977 - Subset(Seventh ACM Egyptian National Programming Contest)

Problem : Subset
Description :

给你一串序列，要你从中选择一个子集使得这个子集的和的绝对值最小，并且子集元素的个数要尽可能小，求这个绝对值和子集的大小。

Solution :

半枚举+上下界二分。我们知道如果枚举整个序列，那么最大要计算$2^{35}=34359738368$, 这么大的计算是无法承受的，但是，我们把这个序列分成两半，那么最多计算$2^{18}=262144$,这是可以承受的。然后我们再把两个子序列合起来，合的时候不能用朴素的方法，不然就没有意义了，我们可以枚举一个序列的元素，然后二分查找另一个序列中的元素，使得这两个序列中的元素尽可能靠近0. 那么这个时候我们要进行两次二分，一次找最接近0的负值，一次找最接近0的正值。然后枚举正值和负值之间的元素。这样可以保证取到所有的解。这个题的数据还是有点弱的，网上很多程序都通过了，其实是不行的，原因就是二分的时候，如果出现sum相等的Node,那么会取到最靠近0的Node，从而使得漏解。最好的做法就是向两边遍历，找到最远的Node，然后再枚举，这样就能保证AC！

Code(C++) :

#include <stdio.h>
#include <string.h>

#include <istream>
#include <algorithm>
#include <vector>

typedef long long LL;

using namespace std;

struct Node{
    LL sum;
    int num;
    Node(){}
    Node(LL sum,int num):sum(sum),num(num){}
};

const int MAXN=35+5;

int n;
LL a[MAXN];
bool LS[MAXN],RS[MAXN];

vector<Node> vL,vR;

LL ansSum;
int ansNum;

LL Abs(LL a)
{
    return a>0? a:-a;
}

bool cmp(Node a,Node b)
{
    if(a.sum!=b.sum)
        return a.sum<b.sum;
    return a.num<b.num;
}

void enumL(int dep)
{
    if(dep==n/2){
        LL sum=0;
        int num=0;
        for(int i=0;i<n/2;i++)
            if(LS[i])
                ++num,sum+=a[i];
        vL.push_back(Node(sum,num));
        return ;
    }
    LS[dep]=false;
    enumL(dep+1);
    LS[dep]=true;
    enumL(dep+1);
}

void enumR(int dep)
{
    if(dep==n-n/2){
        LL sum=0;
        int num=0;
        for(int i=0;i<n-n/2;i++)
            if(RS[i])
                ++num,sum+=a[i+n/2];
        vR.push_back(Node(sum,num));
        return ;
    }
    RS[dep]=false;
    enumR(dep+1);
    RS[dep]=true;
    enumR(dep+1);
}

void deal()
{
    for(unsigned int i=0;i<vL.size();i++){
        LL nowSum=vL.at(i).sum;
        int nowNum=vL.at(i).num;

        int l=0,r=vR.size()-1;
        int L=0,R=r;
        while(l<=r){
            int mid=(r+l)/2;
            if(nowSum+vR.at(mid).sum>=0)
                r=mid-1;
            else
                L=mid,l=mid+1;
        }
        l=0,r=vR.size()-1;
        while(l<=r){
            int mid=(r+l)/2;
            if(nowSum+vR.at(mid).sum>0)
                R=mid,r=mid-1;
            else
                l=mid+1;
        }

        //printf("L:%d R:%d\n",L,R);

        int EL=L,ER=R;
        for(;EL>=0&&vR.at(EL).sum==vR.at(L).sum;EL--);
        for(;ER<vR.size()&&vR.at(ER).sum==vR.at(R).sum;ER++);

        for(int j=EL+1;j<=ER-1;j++){
            LL tmpSum=Abs(nowSum+vR.at(j).sum);
            int tmpNum=vR.at(j).num+nowNum;
            if(tmpNum==0)
                continue;
            if(tmpSum<ansSum){
                ansSum=tmpSum;
                ansNum=tmpNum;
            }else if(tmpSum==ansSum&&ansNum>tmpNum)
                ansNum=tmpNum;
            if(ansSum==0&&ansNum==1)
                return ;
        }
    }
}

int main()
{
    //freopen("in","r",stdin);
    while(scanf("%d",&n),n){
        for(int i=0;i<n;i++){
            scanf("%lld",&a[i]);
        }
        //sort(a,a+n);
        vL.clear();
        vR.clear();

        enumL(0);
        enumR(0);
        sort(vR.begin(),vR.end(),cmp);

        /*
        for(unsigned int i=0;i<vL.size();i++)
            printf("%lld ",vL.at(i));
        puts("");
        for(unsigned int i=0;i<vR.size();i++)
            printf("%lld ",vR.at(i));
        puts("");
        */

        ansSum=(1LL<<50),ansNum=MAXN;
        deal();

        printf("%lld %d\n",ansSum,ansNum);
    }
    return 0;
}