题意:达达帮翰翰给女生送礼物，翰翰一共准备了(N)个礼物，其中第(i)个礼物的重量是(a[i]).达达的力气很大，他一次可以搬动重量之和不超过(M)的任意多个物品。达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少.
一句话题意:从给定的(N(N<=45))个数中选择若干个,使得它们的和最接近(M(M<=2^{31}-1))
分析:如果爆搜的话,有45个数,时间复杂度可以达到(2^{45}),显然超时.但是如果我们把N个数拆成两份,则一次搜索时间复杂度只有(2^{45/2}),是可以接受的.
其实这就是meet in the mid的搜索算法思想.我们把这N个数从中间分成两份,先爆搜第一份,用一个数组b记录所有搜出来的可以达到的值,然后排序并去重,存到c数组中.接着搜索第二份,每搜到一个数sum,在c数组中二分查找(<=m-sum)的数中最大的一个,用这个数与(sum)的和更新答案即可.
对搜索优化一下,我们把a数组从大到小排序再分半搜索,减少状态量.还有如果搜到的数大于m,直接return掉.
因为搜索过程中,sum可能会大于m,也就是可能爆int,所以记得开一下long long.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline ll read(){
ll x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=50;
const int M=5000005;
int n,m,mid,tot,cnt,a[N];
ll ans,b[M],c[M];
inline void dfs1(ll sum,int now){
if(sum>m)return;
b[++tot]=sum;
if(now>mid)return;
dfs1(sum,now+1);
dfs1(sum+a[now],now+1);
}
inline void find(ll x){
int l=1,r=cnt,mmid,t=m-x,en;
while(l<=r){
mmid=(l+r)>>1;
if(c[mmid]<=t){
en=mmid;
l=mmid+1;
}
else r=mmid-1;
}
ans=max(ans,c[en]+x);
}
inline void dfs2(ll sum,int now){
if(sum>m)return;
find(sum);
if(now>n)return;
dfs2(sum,now+1);
dfs2(sum+a[now],now+1);
}
int main(){
m=read();n=read();
for(int i=1;i<=n;++i)a[i]=read();
sort(a+1,a+n+1);reverse(a+1,a+n+1);
mid=n/2+1;dfs1(0,1);
sort(b+1,b+tot+1);c[++cnt]=0;
for(int i=1;i<=tot;++i){
if(b[i]==c[cnt])continue;
c[++cnt]=b[i];
}
dfs2(0,mid+1);
printf("%lld
",ans);
return 0;
}