贪心
思路
与国王游戏的贪心算法类似。
我们先分析:危险值 = 它前面奶牛的重量($w$)之和 - 自身强壮值($s$)。
根据题感,我们可以想出一种做法:因为危险值和 $w$、$s$ 都有关,所以可以将每头牛的 $w + s$ 排序。
证明
如果交换两头奶牛 $i$ 和 $i + 1$:
- 交换前 $i$:$\sum\limits_{j = 1}^{i - 1}{w_j} - s_i$;
交换前 $i + 1$:$\sum\limits_{j = 1}^i{w_j} - s_{i + 1}$。 - 交换后 $i$:$\sum\limits_{j = 1}^{i - 1}{w_j} + w_{i + 1} - s_i$;
交换后 $i + 1$:$\sum\limits_{j = 1}^{i - 1}{w_j} - s_{i + 1}$
其他牛的危险值不受影响。
分析交换前与交换后的式子,进行化简,同时减去 $\sum\limits_{j = 1}^{i - 1}{w_j}$,得到:
- 交换前 $i$:$ - s_i$;
交换前 $i + 1$:$w_i - s_{i + 1}$。 - 交换后 $i$:$w_{i + 1} - s_i$;
交换后 $i + 1$:$ - s_{i + 1}$
由于 $w$、$s$ 都是正数,$w_i - s_{i + 1} > - s_{i + 1}$,$w_{i + 1} -s_i > - s_i$。
当 $w_i − s_{i + 1} \geq w_{i + 1} − s_i$,即 $w_i + s_i \geq w_{i + 1} + s_i + 1$时, 交换后更优。
当 $w_i − s_{i + 1} < w_{i + 1} − s_i$,即 $w_i + s_i < w_{i + 1} + s_i + 1$时, 交换前更优。
做法得证,完结撒花!
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
#define PII pair<int, int>
#define x first
#define y second
const int N = 50010;
int n;
PII cow[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
int w, s;
scanf("%d%d", &w, &s);
cow[i] = make_pair(w + s, w);
}
sort(cow + 1, cow + 1 + n);
int ans = -2e9, sum = 0;
for (int i = 1; i <= n; i ++ )
{
int w = cow[i].y, s = cow[i].x - w;
ans = max(ans, sum - s);
sum += w;
}
printf("%d", ans);
return 0;
}