算法:贪心
时间复杂度:$O(n \times log(n))$
贪心一般很考思维,比较难想,还是需要积累啊!
该题的核心在于找出 $w_i + s_i$ 和 $w_{i + 1} + s_{i + 1}$ 大小关系,才明白为什么需要排序。
位置 | 交换前 | 交换后 |
---|---|---|
第 i 头牛 | $w1 + w2 +…+ wi - 1 - si$ | $w1 + w2 +…+ wi-1 + wi+1 - si$ |
第 i + 1 头牛 | $w1 + w2 +…+ wi-1 + wi - si+1$ | $w1 + w2 +…+ wi-1 - si+1$ |
因为所求的为风险最大的最小值,所以去掉干扰 $w_1+w_2+…+w_{i-1}$,需要比较的是 $w_i-s_{i+1}$ 和 $w_{i+1}-s_i$ 的大小,则:
$$w_i-s_{i+1} > w_{i+1}-s_i \to w_i + s_i > w_{i + 1} + s_{i + 1}$$
而这也是最优解,再只需按 $w_i + s_i$ 从小到大进行排序即可,因为从上述的比较关系可以看出 $w_i + s_i$ 越小,风险值也会越小。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair <int, int> PII;
typedef long long LL;
const int N = 50010;
int n;
PII a[N];
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) {
int w, s;
cin >> w >> s;
a[i] = {w + s, w};
}
sort(a, a + n);
LL sum = 0, res = -1e9 - 1;
for (int i = 0; i < n; ++i) {
int s = a[i].x, w = a[i].y;
res = max(res, sum - (s - w));
sum += w;
}
cout << res << endl;
return 0;
}