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

Sweet_Corn · 2026-02-02 10:59:27 · 题解

题目传送门

本题是一个裸二分答案，判断每个蛋糕材料够不够，如果不够就那万能粉来补，最后如果 k 不小于需要的万能粉就是可以，反之就是不可以。

需要注意：不开 long long 见祖宗、边界不能调小，设 0 到 2 \times 10^9 刚刚好。

代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n, k, a[100005], b[100005];
bool check(int x){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        if(a[i] * x > b[i]){
            sum += a[i] * x - b[i];
            if(sum > k)return 0;
        }
    }
    return sum <= k;
}
signed main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++)cin >> a[i];
    for(int i = 1; i <= n; i++)cin >> b[i];
    int l = 0, r = 2e9, ans = 0;
    while(l <= r){
        int mid = (l + r) / 2;
        if(check(mid)){
            l = mid + 1;
            ans = max(ans, mid);
        }else r = mid - 1;
    }
    cout << ans;
    return 0;
}