算法1
(贪心+排序) $O(nlogn)$
题目已经明示需要排序了,问题是如何定义比较函数使得排序后的奶牛风险值最小,假设奶牛最终按照$c_0,…,c_{i},c_{i+1},…,c_n$已然排好序,那么必然有任何一对$(c_i,c_{i+1})$交换后会导致最大的风险值上升.
假设$W_c=\sum_{k=0}^{i-1}$,$c_{i}$的风险值$r_i=W_c-s_i$,同理$r_{i+1}=W_c+w_i-s_{i+1}$,
交换$(c_i,c_{i+1})$后$r_{i+1}=W_c-s_{i+1}$,$r_i=W_c+w_{i+1}-s_i$,
由于$(c_i,c_{i+1})$以满足最优排序,必然有下式:
$max(W_c-s_i, W_c+w_i-s_{i+1})<max(W_c-s_{i+1},W_c+w_{i+1}-s_i)$,消去公共部分$W_c$得:
$max(-s_i, w_i-s_{i+1})<max(-s_{i+1},w_{i+1}-s_i)$,
比较函数找到了,开始撸代码.
不能说完全相似只能说一模一样的题目
国王游戏
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e4 + 1;
int n;
struct Cow {
int w, s;
}cow[maxn];
signed main() {
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 0; i < n; ++i) cin >> cow[i].w >> cow[i].s;
sort(cow, cow + n, [](Cow& x, Cow&y){
return max(-x.s, x.w - y.s) < max(-y.s, y.w - x.s);
});
int re = -1e9;
int s = 0;
for(int i = 0; i < n; ++i) {
re = max(re, s - cow[i].s);
s += cow[i].w;
}
cout << re << "\n";
}