http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3631
将所有元素分成两堆,分别枚举。
然后对其中一堆再枚举一个a,然后二分查找从另一堆找到b,使得b最接近m-a
于是得到结果。。。
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cmath> using namespace std; int p[31]; int suma[200000],sumb[200000],cnta,cntb; int s[50]; int n,m; void ma(int len){ int i; cnta=0; for(i=0;i<=len;i++) p[i]=0; do{ suma[cnta]=0; for(i=0;i<len;i++) if(p[i]) suma[cnta]+=s[i]; cnta++; p[i=0]++; while(p[i]>1){ p[i]=0; p[++i]++; } }while(p[len]==0); sort(suma,suma+cnta); } void mb(int len){ int i; cntb=0; for(i=0;i<=len;i++) p[i]=0; do{ sumb[cntb]=0; for(i=0;i<len;i++) if(p[i]) sumb[cntb]+=s[i+15]; cntb++; p[i=0]++; while(p[i]>1){ p[i]=0; p[++i]++; } }while(p[len]==0); sort(sumb,sumb+cntb); } int deal(int x){ int l,r,mid; if(x<=0) return 0; l=0,r=cnta-1; suma[cnta]=100100000; while(l<=r){ mid=(l+r)>>1; if(suma[mid]<=x && x<suma[mid+1]) return suma[mid]; if(x<suma[mid]) r=mid-1; else l=mid+1; } return 0; } int main(){ int i,j,res,tmp; while(cin>>n>>m){ for(i=0;i<n;i++) cin>>s[i]; if(n<=15){ ma(n); res=deal(m-0); } else{ ma(15); mb(n-15); res=0; for(i=0;i<cntb;i++){ tmp=sumb[i]+deal(m-sumb[i]); if(tmp>res && tmp<=m) res=tmp; } } cout<<res<<endl; } return 0; }