摘要
Title: 125. 耍杂技的牛
Tag: 贪心、推公式
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

125. 耍杂技的牛

• 题意

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

• 思路

  从题意来看，w越大的放下面越好，s越大的放下面也越好，直觉是 $S[i]+W[i]$ 越大的放越下面，这种就是最优的，让最大的风险值降到最小
  证明略

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-15 17:42:15
  FilePath: \ACM\Acwing\125.py
  LastEditTime: 2022-03-15 17:52:45
  '''
  class COW(object):
      def __init__(self, w=0, s=0): # 可以写出无参的构造函数
          self.w = w
          self.s = s
  
  
  N = int(5e4 + 10)
  
  n = int(input())
  cow = [COW() for _ in range(n)] # 不能 [COW()] * N, 这样每个地址都一样
  
  for i in range(n):
      cow[i].w, cow[i].s = map(int, input().split())
  
  cow.sort(key=lambda x: x.w + x.s)
  
  weight = 0
  ans = -2e9
  
  for i in range(n):
      ans = max(ans, weight - cow[i].s) # 求最大的风险值
      weight += cow[i].w
  
  print(ans)