自动搬运

查看原文

来自洛谷，原作者为

	Mine_King 欢迎访问个人博客：caijimk.netlify.app

搬运于2025-08-24 21:36:25，当前版本为作者最后更新于2019-10-21 19:05:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

在这里观看更佳

这题的总体思路是：二分答案+贪心+dfs验证 首先，二分答案是不用说的，就看贪心和dfs验证。 如果要使得$John$得到至少$m$个木材，那么当然是选择最短的啦。所以可以提前把$John$需要的木材按规格从小到大排序，这就是贪心。
然后dfs就是如果能提供的木材有比$John$需要的第$x$根木材的规格大的（或相等的），那么就试试把这根木材中$John$需要的部分卖给他。不过……
第一行为整数m(m<= 50)表示木材店老板可以提供多少块木材给约翰。
这么大的数，不超时才怪勒！所以我们需要剪枝。有两个剪枝：

1. 可行性剪枝，如果剩余的木材都不够$John$的需要，则return，所以这里需要用到前缀和，还要一个变量存储浪费的木材（即连最短的一根木材都不够）
2. 去重，如果两根木材的规格相同，则可以去重。

有了这两个剪枝，就可以玄学地过了这题了！
上代码！

#include<bits/stdc++.h>
using namespace std;
int n,m,a[55],b[1100];
int w,l,r,mid,tot,sum[1100];//w是多余的木材，tot是总共能提供的木材的量，sum是John需要的木材的前缀和
bool dfs(int x,int l)
{
	if(tot-w<sum[mid]) return 0;//第一个剪枝
	if(x==0) return 1;//x=0表示还需要0根，也就是可以满足条件了，那么返回true
	bool f=0;
	for(int i=l;i<=n;i++)
	 if(a[i]>=b[x])//如果第i根木材可以满足John需要的第x根木材，dfs
	 {
	 	a[i]-=b[x];
	 	if(a[i]<b[1]) w+=a[i];
	 	if(b[x-1]==b[x]) f=dfs(x-1,i);//去重
	 	else f=dfs(x-1,1);
	 	if(a[i]<b[1]) w-=a[i];
	 	a[i]+=b[x];
	 	if(f) return 1;
	 }
	 return 0;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		tot+=a[i];
	}
	cin>>m;
	for(int i=1;i<=m;i++) cin>>b[i];
	sort(b+1,b+m+1);//排序
	for(int i=1;i<=m;i++) sum[i]=sum[i-1]+b[i];//计算前缀和，注意一定要在排序后计算哦！
	while(sum[m]>tot&&m) m--;//如果选最短的m根都超出了能提供的木材的范围，则一定不可行
	l=0,r=m;
	while(l<=r)//二分
	{
		mid=(l+r)/2;
		if(dfs(mid,1)) l=mid+1;
		else r=mid-1;
	}
	cout<<l-1;
	return 0;
}

谢谢您看到这里，如果觉得这篇题解能帮到您，请您给我一个赞，谢谢！