Bakery (USACO Silver 2023 February)

对总共花费的 moonies 数 $s$ 进行二分， $x$ 表示花在 cookies 上的数量， $y$ 表示花在 muffins 上的数量。

有 $x + y = s$ 。

我们有如下约束：

$0 \leq x \leq t_C-1$ (做每个cookie的时间严格大于0)
$0 \leq y \leq t_M-1 \iff 0 \leq s-x \leq t_M-1$ (做每个muffin的时间严格大于0)
$(t_C-x)a_i + (t_M-y)b_i \leq c_i \iff (a_i-b_i)x \geq a_i \cdot t_C + b_i \cdot t_M - b_i \cdot s - c_i$ (每个朋友的等待时间内做完)

所以对于每个 $s$ ，我们可以为 $x$ 生成一个最小和最大可行范围，判断是否存在可行解。

注意在二分判断时，ceil 和 floor 的使用要小心。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll T, n, tc, tm;
ll a[100005], b[100005], c[100005];
 
ll xmin, xmax;
 
int main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld %lld %lld", &n, &tc, &tm);
        for (int i = 0; i < n; i++) {
            scanf("%lld %lld %lld", &a[i], &b[i], &c[i]);
        }
 
        ll l = 0, r = tc+tm-2;
        while (l < r) {
            ll mid = (l+r)/2;
            bool ok = true;
            xmin = max(0LL, mid-tm+1);   // 0 <= s-x <= tm-1
            xmax = min(tc-1LL, mid);
            for (int i = 0; i < n; i++) {
                // (a[i]-b[i])x >= a[i]tc + b[i]tm -b[i]s - c[i]
                ll numerator = a[i]*tc + b[i]*tm - b[i]*mid - c[i];
                ll denominator = a[i]-b[i];
                if (denominator > 0) {
                    xmin = max((ll)ceil((double)numerator/denominator), xmin);
                } else if (denominator < 0) {
                    xmax = min((ll)floor((double)numerator/denominator), xmax);
                } else {
                    if (a[i]*tc + b[i]*tm - b[i]*mid - c[i] > 0)
                        ok = false;
                }
            }
            if (xmin > xmax) ok = false;
            if (ok) r = mid;
            else    l = mid+1;
        }
        printf("%lld\n", l);
    }
 
    return 0;
}