/*
关于五万头牛试图叠罗汉那些事儿
牛: 重量 强壮程度 头上所有重量s - 强壮程度ab = 风险值risk
要求全局风险值最低
假设某个牛排成的队列 最上面的牛编号为1 最下面n
每头牛承受重量是前一项的前缀和
s[1] = 0; s[2] = w[1] + s[1]; …… s[i] = s[i - 1] + w[i - 1];
风险值risk[i] = s[i] - ab[i]; 使得risk[i]中最大值最小;
把任何牛插入队伍 不会影响其头上所有牛 下面所有牛承重要加上这头牛的重量 即风险值增加这头牛的重量
(动归思路待延伸)
部分延伸:假设目前队伍牛已经摞好 此时要插入一头牛 应该插在什么地方呢?
插入一头牛 改变的是下面所有牛的风险值 和 该牛本身新增的风险值。
极限法思考:若一头牛强壮程度无限大 重量无限小 则对应的风险值无限小 把它放在哪最合适呢?最底部。
如果一头牛强壮程度无限大 重量无限大 放哪里合适呢? 最底部。
设相邻的两头牛A B若将A放在B下面 有
1.risk[B] = s[-] - ab[B]
2.risk[A] = s[-] + w[B] - ab[A]
反之 则
3.risk'[A] = s[-] - ab[A]
4.risk'[B] = s[-] + w[A] - ab[B]
比较四项的大小 无需考虑s[-],看两组中哪组最大值的最小值小
即结果为 min(max(-ab[B], w[B] - ab[A]) , max(-ab[A], w[A] - ab[B]))
(补充:为方便比较,将所有值全部加上ab[A] + ab[B],最终风险值再减掉就可以)
(此时即为min(max(ab[A], w[B] + ab[B]), max(ab[B], w[A] + ab[A])))
所以对于任意相邻两头牛 只需计算
-ab[B] \ w[B]-ab[A] \ -ab[A] \ w[A]-ab[B] 四者中最小值
最小值即为两牛组合风险最小值 由前两项计算得最小值获后两项计算得最小值决定了AB的上下关系。
一种贪心方法:计算所有两牛之间的上下关系,最后得解
上述贪心算法存在待解决(证明)问题:
1.相邻牛上下关系在中间插入更多牛后是否会改变
2.是否会构成环
对相邻问题进一步分析
A在B下时 ab[A] w[B] + ab[B] 实际在判断这两组内部关系
ab[B] w[A] + ab[A]
若ab[A] > ab[B]
w[A] + ab[A] > ab[A] > ab[B]
w[B] + ab[B] 未定
在每组中的大小关系 下组中最大的一定是w[A] + ab[A]
上组最最大的分情况讨论
若 ab[A] > w[B] + ab[B] 由于 w[B] > 0 则 两组风险值最大值的最小值一定是 ab[A] (A在B下最优)
若相反,则需比较 w[B] + ab[B] 与 w[A] + ab[A]
进一步分情况讨论
若w[B] < w[A] 则 两组中最大值的最小值是 w[B] + ab[B](A在B下最优)
若w[A] + ab[A] - ab[B] > w[B] > w[A] 两组中最大值的最小值是 w[B] + ab[B] (A在B下最优)
若w[B] > w[A] + ab[A] - ab[B] 则两组中最大值的最小值是 w[A] + ab[A] (B在A下最优)
结论 两头牛若满足ab[A] > ab[B] 则仅在 w[B] + ab[B]> w[A] + ab[A] 时 B在A下 否则 A在B下
同理 若满足ab[B] > ab[A] 则仅在 w[A] + ab[A]> w[B] + ab[B] 时 A在B下 否则 B在A下
所以 在w[B] + ab[B]> w[A] + ab[A]前提下 无论ab[B]与ab[A]大小 B均在A下
可推出 对于相邻的两头牛来说 w[i] + ab[i] 较大的一头会在下面。
设定rank = w+ab
将rank值从大到小排列 rank1在最下方 rankn在最上方
单调值 不会构成环!!
排列确定 接下来只要计算风险值!!
胜利!!
*/
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 50010;
int n;
PII cow[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
int s, w;
scanf("%d%d", &w, &s);
cow[i] = {w + s, w};
}
sort(cow, cow + n);
int res = -2e9, sum = 0;
for (int i = 0; i < n; i ++ )
{
int s = cow[i].first - cow[i].second, w = cow[i].second;
res = max(res, sum - s);
sum += w;
}
printf("%d\n", res);
return 0;
}