P5878

liucr · 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;
}