【题目来源】
学而思编程：奶牛杂技团
【题目描述】
农夫约翰有 \(N\) 头奶牛，编号从 \(1\) 到 \(N\)，打算进行叠罗汉的杂技表演。
进行叠罗汉表演时，奶牛站在彼此的身上，形成一个有一定高度的垂直堆叠。
奶牛们正在试图弄清楚它们在这个堆叠中的位置顺序。
奶牛们有自己的重量 \(W_i\) 和力量 \(S_i\)，一头奶牛倒下的风险等于它身上所有奶牛（不包括它自己）的重量和减去它的力量。
你的任务是确定奶牛的顺序，使奶牛的风险值中的最大值尽可能小。
【输入】
第一行包括一个整数 \(N\)，表示奶牛的数量，其中 \(1≤N≤50000\)
接下来 \(N\) 行，每行两个整数，表示奶牛的重量 \(W_i\) 和力量 \(S_i\)，其中 \(1≤W_i≤10000\) \(1≤S_i≤10^9\)
【输出】
输出一个整数，表示最大风险值的最小可能值
【输入样例】
3
10 3
2 5
3 3
【输出样例】
2
【核心思想】
-
问题分析：给定 \(N\) 头奶牛，每头奶牛有重量 \(W_i\) 和力量 \(S_i\)。需要将奶牛叠起来，每头奶牛的风险值等于它上面所有奶牛的重量和减去它的力量。求一种叠放顺序，使得所有奶牛中的最大风险值尽可能小。这是一个自定义排序贪心问题，关键在于找到最优的排序规则。
-
算法选择：
- 风险值分析：对于第 \(i\) 头奶牛（从下往上数），风险值为 \(\sum_{j=1}^{i-1} W_j - S_i\)
- 排序规则推导：考虑相邻两头奶牛 \(i\) 和 \(i+1\)，交换它们的位置后比较风险值，可以推导出最优排序应按 \(W_i + S_i\) 从小到大排序
- 贪心正确性：按 \(W + S\) 排序可以确保承受能力强（\(S\) 大）且重量轻（\(W\) 小）的奶牛放在下面，从而最小化每头奶牛的风险值
-
关键步骤：
- 读取输入：\(N\)（奶牛数量）、每头奶牛的 \(W_i\) 和 \(S_i\)
- 自定义排序：按 \(W_i + S_i\) 从小到大排序
- 遍历计算风险值（遍历 \(i\) 从 \(1\) 到 \(N\)）：
- 计算当前风险值：
risk = tot - a[i].s（上面所有牛的重量 - 当前牛的力量） - 更新最大风险值：
ans = max(ans, risk) - 累加重量：
tot += a[i].w
- 计算当前风险值：
- 输出结果：最小化的最大风险值 \(ans\)
-
时间/空间复杂度：
- 时间复杂度：\(O(N \log N)\)，主要是排序复杂度
- 空间复杂度：\(O(N)\)，存储奶牛信息
-
自定义排序贪心的核心思想：
- 问题建模：将叠放顺序问题转化为排序问题，通过分析相邻元素交换的影响推导排序规则
- 交换论证：考虑相邻两头奶牛交换位置后的风险值变化，推导出最优排序条件
- 排序规则：按 \(W + S\) 排序，让承受能力强且重量轻的奶牛优先放在下面
- 线性扫描：排序后只需一次线性扫描即可计算最大风险值
- 适用于顺序优化、调度问题、最小化最大值类问题
【算法标签】
贪心
【代码详解】
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n, ans = -1e9, tot; // ans: 最大风险值, tot: 累计总重量
struct node
{int w, s; // w: 牛的重量, s: 牛的强壮程度
} a[50005];// 排序规则：按w+s从小到大排序
bool cmp(node x, node y)
{return x.w + x.s < y.w + y.s;
}int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i].w >> a[i].s;}sort(a + 1, a + n + 1, cmp);for (int i = 1; i <= n; i++){// 当前牛的风险值 = 它上面所有牛的重量 - 它的强壮程度ans = max(ans, tot - a[i].s);tot += a[i].w; // 累计总重量}cout << ans;return 0;
}
【运行结果】
3
10 3
2 5
3 3