ABC374 E 题解

DengStar / 2024-10-06 / 原文

ABC374 E 题解

E - Sensor Optimization Dilemma 2

题目链接：AT | 洛谷

容易发现答案可以二分。于是我们把问题转化为了判定性问题：给定目标 $x$，能否在花费不超过预算的情况下，使得每个过程的产量都不低于 $x$？

进一步，由于各个过程的生产互不相关，所以我们要尽可能让每个过程的费用尽可能小，这样一定是最优的。对于每个过程分别考虑，就是要问：

给定两种机器，第一种机器的产量为 $a$，价格为 $p$；第二种机器的产量为 $b$，价格为 $q$。要使总产量达到 $x$，如何让花费尽可能少？

（其实我从这里开始就想不出来了）

一种显然的暴力是枚举某一种机器的数量——例如第一种，从 $0$ 枚举到 $\left\lceil \dfrac{x}{a} \right\rceil$，同时可以 $O(1)$ 计算出所需的第二种机器的数量。这样算出的答案显然一定正确，但枚举的次数是 $O(x/a)$，当 $x$ 很大且 $a$ 很小时，无法接受。

想到正解或许需要一点灵感。考虑这个事实：如果要生产 $ab$ 个零件，有两种方案：购买 $b$ 个第一种机器，花费 $bp$；或 $a$ 个第二种机器，花费 $aq$。可能还有别的方案，但可以别的证明一定不会更优。（从“性价比”的角度来考虑。）

从这个事实，可以推出：在最优方案中，两种机器的产量不可能同时达到 $ab$。如果两种机器的产量都达到了 $ab$，总可以把较贵的 $ab$ 产量交换给另一种机器，使得费用更低。因此，以下两种情况不可能同时发生：

第一种机器的数量达到 $b$。
第二种机器的数量达到 $a$。

这实际上就是“两种机器的产量不可能同时达到 $ab$”的另一种表述方法。

有了这个结论之后，就可以分别枚举两种机器的数量：第一种机器从 $0$ 枚举到 $b - 1$，第二种机器从 $0$ 枚举到 $a - 1$。根据上述结论，这样就可以保证枚举到最优策略。设 $a$ 与 $b$ 的值域为 $V$，我们就在 $O(\log(XV)NV)$ 的时间内通过了此题。

参考代码：

auto check = [&](const i64 x) -> bool
{
    i64 tot = 0;
    for(int i = 0; i < n; i++)
    {
        i64 a = A[i], b = B[i], p = P[i], q = Q[i], xx = x, add = 0x3f3f3f3f3f3f3f3f;

        for(int j = 0; j < b; j++)
        {
            i64 tmp = j * p + ceil(max(0ll, xx - j * a), b) * q;
            add = min(add, tmp);
        }
        for(int j = 0; j < a; j++)
        {
            i64 tmp = j * q + ceil(max(0ll, xx - j * b), a) * p;
            add = min(add, tmp);
        }

        tot += add;
        if(tot > lim) return false;
    }
    return true;
};

int L = 0, R = 1e9, ans = -1;
while(L <= R)
{
    int mid = (L + R) >> 1;
    if(check(mid)) L = mid + 1, ans = mid;
    else R = mid - 1;
}

提交记录