AcWing 125. 耍杂技的牛

◎

本节目标

从最大风险的相邻交换比较中推导按重量与强壮值之和排序。

这是贪心选择与证明的拓展题。难点不在代码，而在从相邻两头牛的风险比较中推出排序键 w+s。

题意与约束

每头牛有重量 w 与强壮值 s。从上到下叠放时，一头牛的风险定义为它上方所有牛的总重量减去它的强壮值，目标是最小化最大风险。函数返回该最小可能最大风险，风险可以为负。

直接思路与瓶颈

枚举叠放顺序是排列问题。只比较当前最大风险也无法决定下一头牛，因为本次重量会影响之后所有牛的风险。

贪心模型与算法推导

按 w+s 升序排序。扫描时 aboveWeight 保存当前牛上方的总重量；先用 aboveWeight-s 更新最大风险，再加入当前牛重量。这里按题目冻结的风险定义，普通样例 [(3,5),(2,3),(1,4)] 的答案是 -2。

正确性依据

设此前上方重量为 P，相邻牛为 A(w_a,s_a)、B(w_b,s_b)。顺序 A,B 中两者风险上界为 max(P-s_a, P+w_a-s_b)；顺序 B,A 为 max(P-s_b, P+w_b-s_a)。当 w_a+s_a<=w_b+s_b 时，可验证前一种上界不大于后一种。因此逆序的相邻牛交换不会变差，最终按 w+s 升序的排列最优。

样例执行过程

三头牛的 w+s 分别为 8,5,5，排序后可为 (2,3),(1,4),(3,5)。风险依次是 0-3=-3、2-4=-2、3-5=-2，最大值 -2。单头 (5,7) 上方重量为零，风险为 -7。

代码实现

C++

C++17

#include <algorithm>
#include <limits>
#include <utility>
#include <vector>

using namespace std;

long long maxRisk(vector<pair<int, int>> cows) {
    sort(cows.begin(), cows.end(), [](const pair<int, int>& left, const pair<int, int>& right) {
        return static_cast<long long>(left.first) + left.second
            < static_cast<long long>(right.first) + right.second;
    });

    long long aboveWeight = 0;
    long long answer = numeric_limits<long long>::lowest();
    for (const auto& [weight, strength] : cows) {
        answer = max(answer, aboveWeight - strength);
        aboveWeight += weight;
    }
    return answer;
}

Python

Python 3

def max_risk(cows: list[tuple[int, int]]) -> int:
    above_weight = 0
    answer = float('-inf')
    for weight, strength in sorted(cows, key=lambda cow: cow[0] + cow[1]):
        answer = max(answer, above_weight - strength)
        above_weight += weight
    return int(answer)

复杂度分析

排序需要 O(n log n)，扫描需要 O(n)；中间重量和风险使用 long long。

边界与易错点

• 不要把风险写成下方总重量；本题定义是上方总重量减强壮值。
• 先计算当前风险，再累加当前重量。
• 所有风险都可能为负，最大值初始化不能写成零。

模式迁移

面对“排序键不显然”的调度题，先写两个相邻元素交换前后的目标上界，再化简比较式；这比猜测排序规则更可靠。