AcWing 125. 耍杂技的牛
原题链接
中等
作者:
Fairy2.0
,
2025-01-18 16:01:47
,
所有人可见
,
阅读 1
//和国王游戏类似
//国王游戏结论:按照每个大臣左右手数的乘积从小到大排序
//结论:按照每头牛的重量和强壮度的和从小到大排序为最优化
//证明和国王游戏一样
#include <iostream>
#include <algorithm>
#include <cstdio>
#define x first
#define y second
using namespace std;
const int N = 50010;
typedef pair<int , int> PII;
PII cows[N];
int n;
int main (){
scanf ("%d" , &n);
for (int i = 0;i < n;i++){
int w = 0;
int s = 0;
scanf ("%d %d" , &w , &s);
cows[i] = {w + s, w};
}
//按照每头牛的重量和强壮度的和从小到大排序
sort(cows , cows + n);
int res = -1e9;
int cnt = 0;
for (int i = 0;i < n;i++){
res = max(res , cnt - cows[i].x + cows[i].y);
cnt += cows[i].y;
}
cout << res << endl;
return 0;
}