题解：B4465 [海淀区入门组 2025] 制作蛋糕

· · 题解

题解：B4465 [海淀区入门组 2025] 制作蛋糕

link

思路

一道二分答案的经典题。

我们可以在边界设定在 0 到 2 \times 10^9 之间。

我们判断每个蛋糕材料够不够，如果不够就那万能粉来补，最后如果 k 不小于需要的万能粉就是可以，反之则不行。

提示

  1. 不开……见祖宗。
  2. 二分答案一定要更新最大值。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005],b[100005];
int n,k;
bool check(int x){
    int cnt=0;
    for(int i=0;i<n;i++){
        if(a[i]*x>b[i]){
            cnt+=a[i]*x-b[i];
            if(cnt>k)return false;
        }
    }
    return cnt<=k;
}

signed main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    int l=0,r=2000000000,ans=0;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(check(mid)){
            ans=max(ans,mid);
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    cout<<ans;
    return 0;
}