二分 + 上下取整

考虑对 $t_C$ 和 $t_M$ 一起升级了 $sum$ 次，那么 $sum$ 显然具有二段性，可以二分。

对于当前二分到的 $sum$，可以用 $N$ 个不等式求解 $t_C$ 的减少量（即仅对饼干升级的次数），设其为 $s_c$，对应的，$t_M$ 的减少量设为 $s_m$，那么就有 $s_c + s_m = sum$。现在考虑对一组 $a, b, c$，有如下式子成立

$$ \begin{align*} a(t_C - s_c) + b(t_M - s_m) &\leq c, \\ a(t_C - s_c) + b(t_M - (sum - s_c)) &\leq c, \end{align*} $$

最终整理得到

$$ (b - a)s_c \leq c - (a \cdot t_C + b \cdot t_M - b \cdot sum). $$

下面分类讨论。

• $a < b$：$$s_c \leq \lfloor \frac{c - (a \cdot t_C + b \cdot t_M - b \cdot sum)}{b - a} \rfloor,$$
• $a > b$：$$s_c \geq \lceil \frac{c - (a \cdot t_C + b \cdot t_M - b \cdot sum)}{b - a} \rceil,$$
• $a = b$：那么有 $$sum \geq t_C + t_M - \lfloor \frac{c}{a} \rfloor.$$

所以对于 $a = b$ 的情况，可以先预处理，也就是至少需要升级多少次。

对于 $a \neq b$，算出 $s_c$ 的可选区间 $[loc, hic]$ 后，需要判断下面三点

• $loc \leq \min(hic, sum)$；
• $\min(s_c) = loc < t_C$；
• $\min(s_m) = sum - \max(s_c) = sum - \min(hic, sum) < t_M$。

时间复杂度 $O(\sum N\log V)$

• 其中 $V$ 大约是 $2 \cdot 10^9$；
• 实现的时候，上下取整需要利用 C++ 向零取整的特性进行调整。
• 笑点解析：$t_C$ 和 $t_M$ 不能减到 $0$ 😄

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

template<class T>
T floor(T x, T y) {
    assert(y != 0);
    if (x > 0 and y < 0) {
        return -((x - 1) / -y + 1);
    } else if (x < 0 and y > 0) {
        return -((-x - 1) / y + 1);
    }
    return std::abs(x) / std::abs(y);
}
template<class T>
T ceil(T x, T y) {
    assert(y != 0);
    if (x > 0 and y > 0) {
        return (x - 1) / y + 1;
    } else if (x < 0 and y < 0) {
        return (-x - 1) / -y + 1;
    }
    return x / y;
}

void solve() {
    int N, tC, tM;
    std::cin >> N >> tC >> tM;

    i64 up = 1;
    std::vector<std::array<i64, 3>> cus;
    for (int i = 0; i < N; i++) {
        i64 a, b, c;
        std::cin >> a >> b >> c;
        if (a == b) {
            up = std::max(up, tC + tM - c / a);
        } else {
            cus.push_back({a, b, c});
        }
    }
    if (cus.empty()) {
        std::cout << up << "\n";
        return;
    }

    auto check = [&](i64 sum) {
        i64 loc = 0;
        i64 hic = std::numeric_limits<i64>::max();
        for (const auto &[a, b, c]: cus) {
            if (a < b) {
                hic = std::min(hic, floor(c - (a * tC + b * tM - b * sum), b - a));
            } else {
                loc = std::max(loc, ceil(c - (a * tC + b * tM - b * sum), b - a));
            }
        }
        return loc < tC and loc <= std::min(hic, sum) and sum - std::min(hic, sum) < tM;
    };

    i64 lo = up, hi = tC + tM - 2;
    while (lo < hi) {
        i64 m = lo + hi >> 1;
        if (check(m)) {
            hi = m;
        } else {
            lo = m + 1;
        }
    }
    std::cout << hi << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    std::cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}