自动搬运

查看原文

来自洛谷，原作者为

	Cute__yhb **

搬运于2025-08-24 22:58:26，当前版本为作者最后更新于2024-05-16 17:38:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

折半搜索。

看数据范围，$2^{46}$ 肯定炸，但 $2 \times 2^{23}$ 炸不了。

整个数组从中间劈成两半，对于每一半，求出礼物能组成的所有重量数，存在两个数组中。

把其中一个数组排序，遍历另一个数组，二分查找在另一个数组中满足条件的最大值。最后求出所有答案的最大值。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define re register
#define ri register int
#define rll register long long
#define ld long double
#define endl '\n'
#define fi first
#define se second
#define pii pair<int,int>
#define p_q priority_queue
#define iter iterator
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define nep(i,a,b) for(int i=(a);i>=(b);i--)
#define popcount __builtin_popcount
#define pb push_back
#define mem(a,x) memset((a),x,sizeof(a))
#define eps 1e-8
#define oper operator
#define mk make_pair
vector<ll>a,b;
ll n,g[55],w;
void dfs1(int l,int r,ll sum){
	if(l>r){
		if(sum<=w)a.pb(sum);//能搬动
		return ;
	}
	dfs1(l+1,r,sum+g[l]);
	dfs1(l+1,r,sum);
}
void dfs2(int l,int r,ll sum){
	if(l>r){
		if(sum<=w)b.pb(sum);//能搬动
		return ;
	}
	dfs2(l+1,r,sum+g[l]);
	dfs2(l+1,r,sum);
}
int main(){
	cin>>w>>n;
	for(int i=1;i<=n;i++) cin>>g[i];
	dfs1(1,(1+n)/2,0);//前一半
	dfs2((1+n)/2+1,n,0);//后一半
	ll maxx=0;
	sort(b.begin(),b.end());//排序
	for(int i=0;i<a.size();i++){
		ll sum=a[i];
		int l=0,r=b.size()-1,ans=0;
		while(l<=r){//二分查找满足条件的最大值
			int mid=(l+r)/2;
			if(b[mid]+a[i]<=w){
				l=mid+1;
				ans=mid;
			}else r=mid-1;
		}
		sum+=b[ans];
		maxx=max(maxx,sum);
	}
	cout<<maxx;//输出
    return 0;
}