双向搜索的思路别人讲了,这里不再赘述
主要是这题正好要用到查找,就顺便做了个效率测试
别忘记开long long
1、stl
注意ub查的是大于x的数,小于等于的下标减1就行了
不要用成lb
效率
1. mid=n/2:TLE
2. mid=n/2+2:7880ms
优点:好写,懒人福利
缺点:太慢了(STL传统艺能)
void dfs2(int id,int now){
int ret=upper_bound(we+1,we+cnt+1,w-now)-we-1;
ans=max(ans,now+we[ret]);
if(id<=mid)return;
if(now+a[id]<=w)dfs2(id-1,now+a[id]);
dfs2(id-1,now);
}
2、二分
效率
1. mid=n/2:6904ms
2. mid=n/2+2:4002ms
优点:效率高了不少,易扩展
缺点:容易死循环、要背2份板子
void dfs2(int id,int now){
int l=0,r=cnt;
while(l<r){
int mid=l+r+1>>1;
if(we[mid]<=w-now)l=mid;
else r=mid-1;
}
ans=max(ans,now+we[l]);
if(id<=mid)return;
if(now+a[id]<=w)dfs2(id-1,now+a[id]);
dfs2(id-1,now);
}
3、倍增
准确的说叫二进制拆分,但大家都叫倍增,也就这么叫了
效率
1. mid=n/2:5910ms
2. mid=n/2+2:3888ms
优点:效率更高一点,相对更好写
缺点:别忘记判边界
void dfs2(int id,int now){
int l=0;
for(int k=Log2;k>=0;--k)if(l+(1<<k)<=cnt&&we[l+(1<<k)]<=w-now)l+=(1<<k);
ans=max(ans,now+we[l]);
if(id<=mid)return;
if(now+a[id]<=w)dfs2(id-1,now+a[id]);
dfs2(id-1,now);
}
总结
我个人喜欢用倍增,因为相对好写而且效率高一些
当然如果你习惯写二分也是可以的
倍增边界可以是常数,但我这里稍微预处理了一下,也许会快一点?
最后贴代码(别在意我鬼畜的码风)
#include<bits/stdc++.h>
#define int long long
#define N 50
using namespace std;
int w,n,a[N],mid,ans,cnt,we[10000009],Log2;
void dfs1(int id,int now){
if(id>mid)return;
if(now+a[id]<=w){
we[++cnt]=now+a[id];
dfs1(id+1,now+a[id]);
}
dfs1(id+1,now);
}
void dfs2(int id,int now){
int l=0;
for(int k=Log2;k>=0;--k)if(l+(1<<k)<=cnt&&we[l+(1<<k)]<=w-now)l+=(1<<k);
ans=max(ans,now+we[l]);
if(id<=mid)return;
if(now+a[id]<=w)dfs2(id-1,now+a[id]);
dfs2(id-1,now);
}
signed main(){
cin>>w>>n;
mid=(n>>1)+2;
for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
sort(a+1,a+n+1);reverse(a+1,a+n+1);
dfs1(1,0);
sort(we+1,we+cnt+1);
cnt=unique(we+1,we+cnt+1)-(we+1);
for(;(1<<Log2+1)<=cnt;++Log2);
// cout<<cnt<<endl;for(int i=1;i<=cnt;++i)printf("%d ",we[i]);puts("");
dfs2(n,0);
cout<<ans<<endl;
return 0;
}