125 耍杂技的牛（贪心）

àì夳堔傛蜴生んèń 2022-08-28 14:50 161阅读 0赞

**1. 问题描述：**

农民约翰的 N 头奶牛（编号为 1...N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。奶牛们不是非常有创意，只提出了一个杂技表演：叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

**输入格式**

第一行输入整数 N，表示奶牛数量。接下来 N 行，每行输入两个整数，表示牛的重量和强壮程度，第 i 行表示第 i 头牛的重量 Wi 以及它的强壮程度 Si。

**输出格式**

输出一个整数，表示最大风险值的最小可能值。

**数据范围**

1 ≤ N ≤ 50000，  
1 ≤ Wi ≤ 10，000  
1 ≤ Si ≤ 1，000，000，000

**输入样例：**

3  
10 3  
2 5  
3 3

**输出样例：**

2  
来源：[https://www.acwing.com/problem/content/127/][https_www.acwing.com_problem_content_127]

**2. 思路分析：**

首先需要理解题目的意思，我们需要调整奶牛的顺序使得最终奶牛最大风险值尽可能小，这道题目本质上是贪心，其中的思路比较难想，假设我们已经将按照w和s对奶牛排好序了，我们可以考虑第i头奶牛与第i + 1头奶牛进行交换，可以发现交换前后的值的变化为：

交换前：

第i头牛：w1 + w2 + ... wi-1 - si  
第i + 1头牛：w1 + w2 + ... wi-1 + wi - si+1

交换后：

第i头牛：w1 + w2 + ... wi-1 - si+1  
第i + 1头牛：w1 + w2 + ... wi-1 + wi+1 - si

排好序之后可以发现第i头牛交换之后值变小了，所以我们需要使得第i + 1头牛的值也更小那么需要满足wi - si+1 > wi+1 - si，也即wi + si > wi+1 + si+1，所以只要发现逆序之后那么就可以交换逆序的顺序那么交换之后的结果是更小的，所以我们可以采用这样一种策略，根据w + s从小到大排序，这样风险系数的最大值就是我们要求解的答案。

**3. 代码如下：**

if __name__ == '__main__':
        # n为奶牛数量
        n = int(input())
        cows = list()
        for i in range(n):
            w, s = map(int, input().split())
            cows.append((w + s, w))
        # 按照双关键字排序
        cows.sort(key=lambda x: (x[0], x[1]))
        s = 0
        res = -10 ** 10
        w = 0
        for i in range(n):
            s = cows[i][0] - cows[i][1]
            res = max(res, w - s)
            w += cows[i][1]
        print(res)

[https_www.acwing.com_problem_content_127]: https://www.acwing.com/problem/content/127/