自动搬运

查看原文

来自洛谷，原作者为

	AKPC 下次不写拍子我就是苟

搬运于2025-08-24 22:15:12，当前版本为作者最后更新于2023-07-15 10:33:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

可以准备的奖品数量是单调的，即如果能准备 $x$ 个，那么一定能准备 $x-1$ 个，如果不能，那么 $x+1$ 个更不能准备。所以本题具有单调性。

考虑二分。将 $l$ 设为 $0$，$r$ 设为 $m$（不可能有一份奖品低于一块钱），$mid=\dfrac{l+r}{2}$。每次二分判断 $mid$ 件是否可行。如果可行，$mid\to l$，表示继续搜可不可以买更多件，反之 $mid+1\to r$，从前面找答案。

在判断函数中，假设只有 $1$ 种物品，那么我们可以用 $f_i$ 表示花 $i$ 元钱，最多买多少个物品，这类似于背包状态转移。枚举 $i$，当 $f_i\geq x\times mid - y$ 就退出循环，比较 $i$ 和 $m$ 的大小，如果的话就返回否。

如果是不止一件物品的话，我们只要将上述过程重复 $n$ 次，每次循环得到的 $i$ 累加进 $ans$，与 $m$ 比较就行了。如果 $ans\leq m$，就说明 $mid$ 件是可行的。

搜完之后得到的答案即为最终答案。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[101][6],f[100001],l,r;
bool check(int mid){
	int ans=0;
	for (int i=1;i<=n;i++){
		memset(f,0,sizeof(f));bool tmp=0;
		for (int j=0;j<=m;j++){
			if (j>=a[i][3]) f[j]=max(f[j],f[j-a[i][3]]+a[i][2]);
			if (j>=a[i][5]) f[j]=max(f[j],f[j-a[i][5]]+a[i][4]);
			if (f[j]>=a[i][0]*mid-a[i][1]){
				ans+=j,tmp=1;
				break;
			}
		}
		if (!tmp) return 0;
	}
	return ans<=m;
}
signed main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>a[i][0]>>a[i][1]>>a[i][2]>>a[i][3]>>a[i][4]>>a[i][5];
	l=0,r=m;
	while (l<r){
		int mid=(l+r+1)/2;
		if (check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l;
	return 0;
}