题解：P10730 [NOISG 2023 Qualification] Burgers

· · 题解

题意：给定数组 a,b,c，求两个整数使得 x+y 最大且满足 \forall 1 \leq i \leq n,xa_i + yb_i \leq c_i。

给这个式子换个形式：y \leq \frac{c_i-xa_i}{b_i}。

得到 x+y \leq (1-\frac{a_i}{b_i})x + \frac{c_i}{b_i}。

发现这相当于给一些线段，求线段下方最大点。

建出凸包简单维护即可。

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

inline long long read(void) {
    long long x = 0, f = 1; char c = getchar();
    while (c > '9' || c < '0') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - 48, c = getchar();
    return x * f;
}

struct node {
    long double k, b, bg;
} stk[100005];

struct line {
    long double k, b;
    friend bool operator< (line x, line y) {
        if (x. k == y. k) return x. b < y. b;
        return x. k > y. k;
    }
} lne[100005];

long long n, cnt, cct, c[100005], a[100005], b[100005], ans;

int main(void) {
    n = read();
    for (int i = 1; i <= n; i++) c[i] = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) b[i] = read();
    if (a[1] < b[1]) for (int i = 1; i <= n; i++) swap(a[i], b[i]);
    for (int i = 1; i <= n; i++) lne[i]. k = (long double)1 - (long double)(a[i]) / b[i], lne[i]. b = (long double)c[i] / b[i];
    sort(lne + 1, lne + 1 + n);
    for (int i = 1; i <= n; i++)
        if (i == 1 || lne[i]. k != lne[i - 1]. k)
            lne[++cct] = lne[i];
    n = cct;
    stk[++cnt] = {lne[1]. k, lne[1]. b, 0};
    for (int i = 2; i <= n; i++) {
        while (cnt && (lne[i]. b - stk[cnt]. b) / (stk[cnt]. k - lne[i]. k) <= stk[cnt]. bg) cnt--;
        if (!cnt) stk[++cnt] = {lne[i]. k, lne[i]. b, 0};
        else cnt++, stk[cnt] = {lne[i]. k, lne[i]. b, (lne[i]. b - stk[cnt - 1]. b) / (stk[cnt - 1]. k - lne[i]. k)};
    }
    for (int i = 1; i <= cnt; i++) {
        if (i == cnt || ceill(stk[i]. bg) < stk[i + 1]. bg) ans = max(ans, (long long)(ceill(stk[i]. bg) * stk[i]. k + stk[i]. b));
        if (i < cnt && floor(stk[i + 1]. bg) >= stk[i]. bg) ans = max(ans, (long long)((floor(stk[i + 1]. bg)) * stk[i]. k + stk[i]. b));
    }
    printf("%lld", ans);
    return 0;
}