ABC374 E 题解
E - Sensor Optimization Dilemma 2
容易发现答案可以二分。于是我们把问题转化为了判定性问题：给定目标 \(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;
}