[USACO23FEB] Bakery S

题目描述

Bessie 开了一家面包店!

在她的面包店里，Bessie 有一个烤箱，可以在 $t_C$ 的时间内生产一块饼干或在 $t_M$ 单位时间内生产一块松糕。
$(1\le t_C,t_M\le 10^9)$。由于空间限制，Bessie 一次只能生产一种糕点，所以要生产 $A$ 块饼干和 $B$ 块松饼，需要 $A\cdot t_C+B\cdot t_M$ 单位的时间。

Bessie的 $N(1\le N\le 100)$ 朋友都想一个一个地去面包店。第 $i$ 个朋友一进门就会点 $a_i(1\le a_i\le 10^9)$ 块饼干和 $b_i(1\le b_i\le 10^9)$ 块松饼。Bessie 没有空间来储存糕点，所以她只有在接到订单后才开始制作糕点。此外，Bessie 的朋友都很忙，所以第 $i$ 个朋友只愿意等 $c_i(a_i+b_i\le c_i\le 2\cdot 10^{18})$ 个单位的时间，然后就伤心地离开。

Bessie 真的不希望她的朋友们伤心，她可以用一块钱升级她的烤箱，让它少花一个单位的时间来生产一块饼干或少花一个单位的时间来生产一个松饼。她不能将她的烤箱升级到花费小于等于 $0$ 的时间，但她可以选择在她的朋友到来之前将她的烤箱升级多少次，只要生产一块饼干和生产一个松饼所需的时间都严格保持为正数。

对于每一个 $T(1\le T\le 100)$ 的测试案例，请帮助 Bessie 找出她必须花费的最小的钱数量，以便她的面包店能够满足所有的朋友。

输入格式

第一行包含 $T$，测试案例的数量。

每个测试用例都以一行开始，包含 $N$,$t_C$,$t_M$。然后，接下来的 $N$ 行各包含三个整数 $a_i,b_i,c_i$。

测试案例用换行符隔开。

输出格式

Bessie 需要为每个测试案例花费的最少钱数，每行一个。

样例解释 1

在第一个测试案例中，贝西可以支付 $11$ 元来减少 $4$ 单位生产一块饼干所需的 时间和 $7$ 单位生产一块松饼所需的时间，从而使她的烤箱在 $3$ 单位的时间内生产饼干，在 $2$ 单位的时间内生产松饼。那么她可以在 $18$ 单位的时间内满足第一个朋友，在 $14$ 单位的时间内满足第二个朋友，在 $5$ 单位的时间内满足第三个朋友，所以他们都不会伤心而离开。

在第二个测试案例中，贝西应该把生产一块饼干的时间减少 $6$ 单位，把生产一块松饼的时间减少 $0$ 单位。

数据规模与约定

• 输入 $2-4$：$N\le 10,t_C,t_M\le 1000$
• 输入 $5-11$，没有额外的约束。

输入 1

23 7 9
4 3 18
2 4 19
1 1 65 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 22

输出 1

11
6

解析

错误想法：读完题考虑到如果饼干机升级 $k$ 次满足答案，那么 $k-1$ 肯定也满足，所以最开始就想着对饼干机的速度进行二分答案，然后算出面包机的最小升级次数，然后对答案取 $min$，WA了，原因是题目要求是两个机器升级次数的和最少，因此对于单单一个机器二分答案，得到的两者升级次数并不具有单调性，因此不正确。

正确想法：设饼干机和面包机的速率分别为 $x,y$，可以发现二分 $x+y$ 是单调的，因为题目要求速度不能减少为 $0$，因此 $x+y$ 最小值为 $2$，最大值为 $tx+ty$，也就是我们二分的左右边界，现在问题是 check 函数怎么验证合法性？

对于任意的 $i$，都需要满足 $ax+by\le c$，等价于 $ax-bx\le c-bx-by$，再等价于 $(a-b)x\le c-b(x+y)$，而自己 $x+y$ 又刚好是我们二分的值，因此未知数只有一个 $x$，因为是不等式，所以我们需要考虑 $(a-b)$ 的正负性。

• 如果 $a>b$，那么 $x\le (c-b(x+y))/(a-b)$，因为要求速度为正整数，因此需要向下取整。
• 如果 $a<b$，那么 $x\ge (c-b(x+y))/(a-b)$，因为要求速度为正整数，因此需要向上取整。
• 如果 $a==b$，那么左边式子为 $0$，仅需要满足右边式子大于等于 $0$ 即可满足不等式，如果右边式子小于 $0$，那么表示不合法。

遍历完之后我们可以得到 $x$ 的左右取值范围 $x_l,x_r$，怎么证明解合法呢，需要满足以下条件。

• 因为题目要求速度不能少于 $1$，因此 $x$ 最小为 $1$，最大不超过 $x+y-1$。
• 左边界肯定得小于等于右边界，因此 $x_l\le x_r$。
• 右边界不能低于 $1$，左边界不能高于 $tx$，因此 $x_r\ge 1$，$x_l\le tx$。
• 我们的对象都是饼干机 $x$，但同时也需要满足面包机 $y$ 也要合法，因此需要满足 $x+y-x_r\le ty$。

此时我们就完成了 check 函数的验证，二分求出 $x+y$ 的最大值就可以获得最小花费。

代码实现

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pi acos(-1)
const int N = 1e6 + 5, mod = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> PII;
ll n, tx, ty, a[N], b[N], c[N];
bool check(ll sum) {//x + y的速度ll x_l = 1, x_r = sum - 1;for (int i = 1; i <= n; i++) {if (a[i] > b[i]) x_r = min(x_r, (c[i] - b[i] * sum) / (a[i] - b[i]));else if (a[i] < b[i]) x_l = max(x_l, (ll)ceil((c[i] * 1.0 - b[i] * sum) / (a[i] - b[i])));else if (c[i] - b[i] * sum < 0) return false;}if (x_l > x_r || x_r < 1 || x_l > tx || sum - x_r > ty) return false;return true;
}
void solve()
{scanf("%lld%lld%lld", &n, &tx, &ty);for (int i = 1; i <= n; i++) scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);ll l = 2, r = tx + ty, ans = -1;while (l <= r) {ll mid = l + r >> 1;if (check(mid)) ans = mid, l = mid + 1;else r = mid - 1;}printf("%lld\n", tx + ty - ans);
}
int main()
{// freopen("input.txt","r",stdin);// freopen("output.txt","w",stdout);int t = 1;scanf("%d", &t);while (t--) solve();return 0;
}