[Extremely Easy] P10730 [NOISG 2023 Qualification] Burgers

简要题意

有两种汉堡，$n$ 种食材，食材 $i$ 有 $x_i$ 份。

第一种汉堡需要用 $a_i$ 份食材 $i$，第二种汉堡需要用 $b_i$ 份食材 $i$。求出你最大可以做出多少个汉堡。

$1\leq n\leq 10^5$。

思路

设 $f(x)$ 表示钦定做 $x$ 个第一种汉堡，最多可以做出多少个汉堡，那么不难写出式子：

$$f(x)=x+\min_{k=1}^{n}\left\lfloor\frac{x_i-a_ix}{b_i}\right\rfloor$$

其中值域 $\left[0,\min_i \lfloor\frac{x_i}{a_i}\rfloor\right]\cap \mathbb{Z}$。

根据下取整的性质，不难稍作变形：

$$f(x)=x+\min_{k=1}^{n}\left\lfloor\frac{x_i-a_ix}{b_i}\right\rfloor=x+\left\lfloor\min_{k=1}^{n} -\frac{a_i}{b_i}x+\frac{x_i}{b_i}\right\rfloor=\left\lfloor\min_{k=1}^{n}(-\frac{a_i}{b_i}+1)x+\frac{x_i}{b_i}\right\rfloor$$

那么我们需要解决下面一个问题：

给定 $n$ 个一次函数 $f_i$，你需要在给定值域 $S$ 中找到一个 $x$，使得 $\min_i f_i(x)$ 最大。求出这个最大值。

一些比较笨的方法是李超线段树或者凸包，但是更加容易想到的方法是二分这个最大值 $v$，那么只需要判断 $S$ 与所有 $\{x\mid f_i(x)\geq v\}$ 的交是否为 $\varnothing$，而这是容易的。

时间复杂度 $O(n\log V)$，其中 $V$ 为值域。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
using f64 = double;
const f64 eps = 1e-9;

int dcmp(f64 x){ return x < -eps ? -1 : x > eps; }

struct line {
    f64 k, b;
} l[N];
int n, a[N], b[N], x[N], maxR;

bool check(f64 v){
    f64 L = 0, R = maxR;
    for(int i=1;i<=n;i++){
        if(!dcmp(l[i].k)){
            if(dcmp(v - l[i].b) > 0) return false;
            continue;
        }
        f64 x = (v - l[i].b) / l[i].k;
        if(dcmp(l[i].k) == 1) L = max(L, x);
        else R = min(R, x);
        if(dcmp(L - R) > 0) return false;
    }
    return ceil(L) <= floor(R);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n, maxR = 1e9;
    for(int i=1;i<=n;i++) cin >> x[i];
    for(int i=1;i<=n;i++) cin >> a[i], maxR = min(maxR, x[i] / a[i]);
    for(int i=1;i<=n;i++) cin >> b[i];
    for(int i=1;i<=n;i++) l[i] = {-1.0 * a[i] / b[i] + 1, 1.0 * x[i] / b[i]};
    int L = 0, R = 1e9;
    while(L < R){
        int mid = (L + R + 1) / 2;
        if(check(mid)) L = mid;
        else R = mid - 1;
    }
    cout << R << '\n';
    return 0;
}

// Written by xiezheyuan