AcWing 125. 耍杂技的牛
原题链接
中等
作者:
潘达达
,
2024-10-19 13:33:18
,
所有人可见
,
阅读 3
/*
交换前 交换后
第i头牛 -si wi+1 - si
第i + 1头牛 wi - si+1 -si+1
wi + si > wi+1 + si+1,即每头牛(w+s)值越大,越应该排在后面
*/
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 5e4 + 10;
typedef pair<int, int> PII;
PII cow[N];
int n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int w, s;
scanf("%d%d", &w, &s);
cow[i] = {w + s, s};
}
sort(cow, cow + n);
int res = -1e9, sum = 0;
for (int i = 0; i < n; i++)
{
int w = cow[i].first - cow[i].second, s = cow[i].second;
res = max(res, sum - s);
sum += w;
}
printf("%d\n", res);
return 0;
}