滨州市网站建设_网站建设公司_UI设计_seo优化

欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总贴：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