KUHAR

Adolfo_North · 2022-10-03 18:31:54 · 题解

这是我做过最难的二分了，老师讲了好久我才听懂，这篇题解也算对老师所讲的内容的复习吧！

答案具有明显的单调性，可以考虑二分答案判定的做法，重点在于怎么判定答案是否可行。

对于答案 x，我们需要求每种食材至少需要花多少钱，这些钱的总和如果 \le m，答案可行，尝试变小；答案不可行，需要变大。

但是如何求每种食材至少需要花多少钱呢？由于每种食材只有 2 种型号(小包和大包)，可以枚举小包数量，大包数量即可算出来，从而求出花费。

#include<bits/stdc++.h>
using namespace std;
const int M=105;
int n,m,a[M],b[M],sm[M],pm[M],sv[M],pv[M],ans;
int calc(int v,int i){ //计算需要v份第i食材至少需要多少钱
    if(v<=0) return 0;
    int k=(v-1)/sm[i]+1; //全买小包需要k包
    int r=k*pm[i]; //全买小包的费用
    for(int j=0; j<k; j++){ //枚举买小包的数量
        int t=v-sm[i]*j; //剩余t份需要买大包
        int w=(t-1)/sv[i]+1; //大包需要w包
        r=min(r, j*pm[i]+w*pv[i]); //求最小费用
    }
    return r;
}
bool check(int x){ //判断能否做x道菜
    int s=0;
    for(int i=1; i<=n; i++){
        s+=calc(x*a[i]-b[i],i);
        if(s>m) return 0;
    }
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    int le=0, ri=0; //或者极限ri=100*m;
    for(int i=1; i<=n; i++){
        scanf("%d%d%d%d%d%d",&a[i],&b[i],&sm[i],&pm[i],&sv[i],&pv[i]);
        ri=max(ri,(b[i]+max(m/pm[i]*sm[i], m/pv[i]*sv[i]))/a[i]);//计算可能的最大右端点。
    }
    while(le<=ri){
        int mid=le+ri>>1;
        if(check(mid)){ ans=mid; le=mid+1;}
        else ri=mid-1;
    }
    printf("%d",ans); 
    return 0;
}