AcWing 125. 耍杂技的牛 (推公式)

农民约翰的N头奶牛（编号为1.. N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。

奶牛们不是非常有创意，只提出了一个杂技表演：

叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。

奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这N头奶牛中的每一头都有着自己的重量w i以及自己的强壮程度s i

一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

输入格式

第一行输入整数N，表示奶牛数量。

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

输出格式

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

思路

按照s[i]+w[i]从小到大排序 求最大值

设按照上述规则求得的答案为可行解cnt 最优解为ans

∴ \therefore∴ans≤cnt

∴ \therefore∴ 交换后最大风险值的最小可能指变小了说明原思路正确

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 50010;
int n;
struct Node {
  int s, w;
}node[N];
bool cmp(Node a, Node b) {
  return a.s + a.w < b.s + b.w;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &node[i].w, &node[i].s);
  }
  sort(node, node + n, cmp);
  LL sum = 0, res = -2e9;
  for (int i = 0; i < n; ++i) {
    res = max(res, sum - node[i].s);
    sum += node[i].w;
  }
  printf("%lld\n", res);
  return 0;
}