学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考白银组别比赛学习过程中的题目，记录每一个瞬间。
附上汇总贴：USACO历年白银组真题解析 | 汇总-CSDN博客
【题目描述】
Bessie 开了一家面包店!
在她的面包店里，Bessie 有一个烤箱，可以在 tC 的时间内生产一块饼干或在 tM 单位时间内生产一块松糕。 (1≤tC,tM≤10^9)。由于空间限制，Bessie 一次只能生产一种糕点，所以要生产 A 块饼干和 B 块松饼，需要 A⋅tC+B⋅tM 单位的时间。
Bessie的 N(1≤N≤100) 朋友都想一个一个地去面包店。第 i 个朋友一进门就会点 ai(1≤ai≤10^9) 块饼干和 bi(1≤bi≤10^9) 块松饼。Bessie 没有空间来储存糕点，所以她只有在接到订单后才开始制作糕点。此外，Bessie 的朋友都很忙，所以第 i 个朋友只愿意等 ci(ai+bi≤ci≤2⋅10^18) 个单位的时间，然后就伤心地离开。
Bessie 真的不希望她的朋友们伤心，她可以用一块钱升级她的烤箱，让它少花一个单位的时间来生产一块饼干或少花一个单位的时间来生产一个松饼。她不能将她的烤箱升级到花费小于等于 0 的时间，但她可以选择在她的朋友到来之前将她的烤箱升级多少次，只要生产一块饼干和生产一个松饼所需的时间都严格保持为正数。
对于每一个 T(1≤T≤100) 的测试案例，请帮助 Bessie 找出她必须花费的最小的钱数量，以便她的面包店能够满足所有的朋友。
【输入】
第一行包含 T，测试案例的数量。
每个测试用例都以一行开始，包含 N ,tC,tM。然后，接下来的 N 行各包含三个整数 ai,bi,ci。
测试案例用换行符隔开。
【输出】
Bessie 需要为每个测试案例花费的最少钱数，每行一个。
【输入样例】
2
3 7 9
4 3 18
2 4 19
1 1 6
5 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 22【输出样例】
11
6【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
int T, tc, tM, n;
struct node {
int a, b, c;
}p[105];
bool check(int t)
{
int lower = max(0LL, t-tM+1);
int upper = min(t, tc-1);
for (int i=1; i<=n; i++) {
if (lower>upper) {
return false;
}
int a = p[i].a, b = p[i].b;
int m = a*tc + b*tM - p[i].c;
if (m<=0) continue;
if (a==b) {
if (a*t<m) return false;
} else if (a>b) {
int x = (m-b*t)/(a-b);
if ((m-b*t) % (a-b) && (m-b*t)*1.0/(a-b)>0) {
x++;
}
if (x>upper) return false;
lower = max(lower, x);
} else {
int x = (m-b*t)/(a-b);
if ((m-b*t) % (a-b) && (m-b*t)*1.0/(a-b)<0) {
x--;
}
if (x<lower) return false;
upper = min(upper, x);
}
}
return true;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> T;
while (T--) {
cin >> n >> tc >> tM;
for (int i=1; i<=n; i++) {
cin >> p[i].a >> p[i].b >> p[i].c;
}
int l=0, r = tc+tM-2, ans=r;
while (l<=r) {
// cout << "enter here" << endl;
int mid = (l+r)>>1;
if (check(mid)) {
ans = mid;
r = mid-1; // 如果mid可以满足要求，那就减少的再少一点（题目要求求最小值）
} else {
l = mid+1; // 否则，那就减少的再多点
}
}
cout << ans << endl;
}
return 0;
}【运行结果】
2
3 7 9
4 3 18
2 4 19
1 1 6
11
5 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 22
6
