欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年黄金组真题解析 | 汇总
P1842 奶牛玩杂技
【题目来源】
洛谷：P1842 [USACO05NOV] 奶牛玩杂技 - 洛谷
【题目描述】
Farmer John 养了 \(N\) 头牛，她们已经按 \(1\sim N\) 依次编上了号。FJ 所不知道的是，他的所有牛都梦想着从农场逃走，去参加马戏团的演出。可奶牛们很快发现她们那笨拙的蹄子根本无法在钢丝或晃动的的秋千上站稳（她们还尝试过把自己装在大炮里发射出去，但可想而知，结果是悲惨的） 。最终，她们决定练习一种最简单的杂技：把所有牛都摞在一起， 比如说， 第一头牛站在第二头的身上， 同时第二头牛又站在第三头牛的身上...最底下的是第 \(N\) 头牛。
每头牛都有自己的体重以及力量，编号为 \(i\) 的奶牛的体重为 \(W_i\)，力量为 \(S_i\)。
当某头牛身上站着另一些牛时它就会在一定程度上被压扁，我们不妨把它被压扁的程度叫做它的压扁指数。对于任意的牛，她的压扁指数等于摞在她上面的所有奶牛的总重（当然不包括她自己）减去它的力量。奶牛们按照一定的顺序摞在一起后， 她们的总压扁指数就是被压得最扁的那头奶牛的压扁指数。
你的任务就是帮助奶牛们找出一个摞在一起的顺序，使得总压扁指数最小。
【输入】
第一行一个整数 \(N\)。
接下来 \(N\) 行，每行两个整数 \(W_i\) 和 \(S_i\)。
【输出】
一行一个整数表示最小总压扁指数。
【输入样例】
3
10 3
2 5
3 3
【输出样例】
2
【算法标签】
《洛谷 P1842 奶牛玩杂技》 #贪心# #USACO#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int MAX_N = 50004; // 定义最大牛的数量
int n; // 牛的数量
int res = -1e9; // 存储最终结果（最大风险值）
int t; // 当前累积的重量// 定义牛的结构体，包含重量和力量
struct Node
{int w; // 牛的重量int s; // 牛的力量// 重载小于运算符，用于排序bool operator < (Node &t) {return w + s < t.w + t.s;}
} a[MAX_N]; // 存储所有牛的信息int main()
{// 输入牛的数量cin >> n;// 输入每头牛的重量和力量for (int i = 1; i <= n; i++)cin >> a[i].w >> a[i].s;// 按照w+s升序排序sort(a + 1, a + n + 1);// 计算最大风险值for (int i = 1; i <= n; i++){// 当前牛的风险值 = 上方所有牛的重量 - 当前牛的力量res = max(res, t - a[i].s);// 累加当前牛的重量t += a[i].w;}// 输出结果cout << res << endl;return 0;
}
【运行结果】
3
10 3
2 5
3 3
2