AcWing 171. 送礼物
原题链接
简单
作者:
追着你行走
,
2021-02-04 21:03:30
,
所有人可见
,
阅读 403
来点稍稍不同的, 用枚举的方法来做一下吧,
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5,inf=1<<29;
const double eps=1e-6;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
ll w,n,g[maxn],ar[maxn],cnt;
//二分查找
int find(ll x) {
int l=1,r=cnt ;
while(l<r) {
int mid=(l+r+1)/2;
if(ar[mid]<=x) l=mid;
else r=mid-1;
} return max(0,l);
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
cin>>w>>n;
for(int i=1;i<=n;i++) cin>>g[i];
sort(g+1,g+1+n,greater<ll>() ) ;
for(int i=0;i<(1<<(n/2) );i++ ) { //前一半
ll sum=0;
for(int x=i;x;x-=x&-x) {
int nx=x&-x;
int id=log2(2*nx) ;
sum+=g[id];
if(sum>w) break;
}
if(sum<=w) ar[++cnt]=sum;
}
sort(ar+1,ar+1+cnt); //排序
cnt=unique(ar+1,ar+1+cnt)-ar-1;//去重
//后一半
ll ans=0;
for(int i=0;i<(1<<(n-n/2));i++) {
ll sum=0;
for(int x=i;x;x-=x&-x) {
int nx=x&-x;
int id=log2(2*nx)+n/2;
sum+=g[id];
if(sum>w) break;
}
if(sum<=w) {
int t=find(w-sum);
ans=max(ans,sum+ar[t]);
}
} cout<<ans<<endl;
return 0;
}