题解：P10730 [NOISG 2023 Qualification] Burgers

· · 题解

Statement

为了避免歧义，这里用 x, y 分别指代两种糖数量，用 c_i 表示原文 x_i。

可以认为是 \forall i, a_i x + b_i y \le c_i， 求最大的 x + y。

Sol

几何意义上这是求一个（二维）凸包内 x+y 最大的点，可以用一些很 fancy 的算法解决，但是都很难。考虑转化一下。

二分答案，假设 x + y = d。思考下怎么验证。

可以通过消掉 y 的方式求出 x 的范围。

&a_ix + b_i y \le c_i \\ \Rightarrow & (a_i - b_i) x + b_i(x+y) \le c \\ \Rightarrow & (a_i - b_i) x \le c - b_i d \\ \end{aligned}

分类讨论 a_i - b_i。不难得到

\begin{cases} x &\le \dfrac{c-b_id}{a_i - b_i} & \ \ \ \ a_i > b_i\\ 0 &\le c - b_id & \ \ \ \ a_i = b_i \\ x &\ge \dfrac{c-b_id}{a_i - b_i} & \ \ \ \ a_i < b_i\\ \end{cases}

check 的时候只需要保证第二种情况得到满足，第一、三种解出来不是空集就可以。当然注意 x 是整数，第一种情况下商直接下取整，第二种上取整即可。

Code

#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
using namespace std;
int n, ans = 0;
vector<long long> a, b, c;
bool check(int d){ // if x + y = d has solution
    long long maxx = d, minx = 0;
    for(int i = 0; i < n && minx <= maxx; i++){
        if(a[i] > b[i]) 
            maxx = min(maxx, (c[i] - b[i] * d) / (a[i] - b[i]));
        else if (a[i] < b[i])
            minx = max(minx, (c[i] - b[i] * d -1) / (a[i] - b[i]) + 1);
        else if (a[i] * d > c[i]) return false;
    }
    return minx <= maxx;
}
int main(){
    ios::sync_with_stdio(0),
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(auto vec:{&c, &a, &b}){
        vec->resize(n);
        for(long long&vx:(*vec))
            cin >> vx;
    }
    for(int k = (1<< 30); k; k>>=1){
        if(ans + k < 1e9 && check(ans+k))
            ans += k;
    }
    cout << ans << endl;
}