本文主要是介绍poj 3977 折半枚举+二进制枚举+二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
拿到这道题的时候就想到折半枚举+二分。首先想到的是讲数组分成折半成正负两个数组再进去二分查找。想想就不对。
正确的方法应该是直接将数组折半。然后遍历另一半，寻找最近的和。
#include <iostream>
#include <math.h>
#include <cstdio>
#include <algorithm>
using namespace std;
#define INF 1000000000000000LL
#define LL long long
LL minn,sum;
LL a[40],k;
int n;
struct C
{LL sum,num;
}c[1<<18],s[1<<18];
bool cmp(C &a,C &b)
{if(a.sum-b.sum)return a.sum<b.sum;return a.num<b.num;
}
LL lower_bound(LL sum) //STL 不知道怎么搜索结构体，然后就自己写了。
{LL l=0,r=k-1,mid; while(r>=l) { mid=(r+l)/2; if(s[mid].sum==sum) return mid; else if(s[mid].sum>sum) r=mid-1; else l=mid+1; } return r+1;
}
LL ABS(LL a) //必须自己写。
{return a>=0?a:-a;
}
void solve()
{minn=INF;sum=INF;int len=n/2;for(int i=0;i< 1<<len;i++) {c[i].num=c[i].sum=0;for(int j=0;j<len;j++)if((i>>j)&1)c[i].sum+=a[j],c[i].num++;} sort(c,c+(1<<len),cmp);k=0;s[k++]=c[0];for(int i=1;i< 1<<len;i++)if(c[i].sum>s[k-1].sum)s[k++]=c[i];else if(c[i].sum==0&&s[k-1].sum==0&&s[k-1].num==0) s[k++]=c[i]; //折半完成。int len2=n-len;for(int i=0;i< 1<<len2;i++){LL num=0,ans=0;for(int j=0;j<len2;j++)if(i>>j&1)ans+=a[len+j],num++; LL id=lower_bound(-ans); //寻找与其最近的和。for(LL j=(id-3>=0?id-3:0); j<(id+3<k?id+2:k); j++) //在一个范围内寻找。{if(num+s[j].num!=0){if(ABS(ans+s[j].sum)<minn) { minn=ABS(ans+s[j].sum); sum=num+s[j].num; } else if(ABS(ans+s[j].sum)==minn&&num+s[j].num<sum) sum=num+s[j].num; }}}cout<<minn<<" "<<sum<<endl;
}
int main()
{while (scanf("%d",&n) , n) {for(int i=0;i<n;i++)scanf("%lld",&a[i]);solve();}return 0;
}这篇关于poj 3977 折半枚举+二进制枚举+二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
