解题思路
贪心策略
本次采用贪心算法,根据题意易得出贪心策略为:按$w_i + s_i$从大到小的顺序从下往上叠罗汉。
正确性证明
设原来的顺序为$…w_i w_j…$($w_i + s_i > w_j + s_j$)变成$…w_j w_i…$之后观察风险最大值(只考虑发生变化的两个风险值)的变化:(s是上面牛的重量之和)
$$max(s - s_i, s + w_i - s_j)$$变成$$max(s - s_j, s + w_j - s_i)$$
经过对比之后发现交换之后最大值变大了,所以不能交换,所以贪心策略有效
代码
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 50010;
int n;
PII a[N];
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i ++ )
{
int w, s;
scanf("%d%d", &w, &s);
a[i] = {w + s, w};
}
sort(a, a + n);
int sum = 0, res = -2e9;
for(int i = 0; i < n; i ++ )
{
res = max(res, sum - (a[i].first - a[i].second));
sum += a[i].second;
}
printf("%d", res);
return 0;
}