题解：P10730 [NOISG 2023 Qualification] Burgers

zhang_kevin · 2025-12-02 22:25:11 · 题解

显然答案具有单调性，故可以进行二分答案。

令 mid 表示二分到的答案。不妨假设第一种汉堡你制作了 x 个，则可以计算出另一种汉堡制作了 mid - x 个。

对于每个 i，成功制作汉堡需要满足以下不等式：

由于 x 是未知的，故把未知变量 x 和其他分开：

然后就可以分情况讨论了：

经过上述分析，我们可以判断 x 的上下界。但是注意，除此之外我们还需要满足两个汉堡制作数量非负，因此 x \in [0, mid]。

综上，我们在 \mathcal{O}(n \log V) 的时间复杂度内解决了这个题目。

参考代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
typedef long long ll;
int n, x[100005], a[100005], b[100005];
inline bool check(int mid){
    ll Max = 1e18, Min = -1e18;
    for(int i = 1; i <= n; i++){
        if(a[i] == b[i]){
            if((ll)x[i] < (ll)b[i] * mid){
                return false;
            }
            continue;
        }
        double need = 1.0 * ((ll)x[i] - (ll)b[i] * mid) / (a[i] - b[i]);
        if(a[i] - b[i] > 0){
            Max = min(Max, (ll)floor(need));
        }else{
            Min = max(Min, (ll)ceil(need));
        }
    }
    return max(Min, 0ll) <= min(Max, (ll)mid);
}
signed main(){
    n = read();
    for(int i = 1; i <= n; i++) x[i] = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 1; i <= n; i++) b[i] = read();
    int l = 0, r = 1e9, ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid)){
            ans = mid;
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    cout << ans << '\n';
    return 0;
}