农民约翰的N头奶牛（编号为1…N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。
奶牛们不是非常有创意，只提出了一个杂技表演：
叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这N头奶牛中的每一头都有着自己的重量Wi以及自己的强壮程度Si。
一头牛只撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。
输入格式
第一行输入整数N，表示奶牛数量。
接下来N行，每行输入两个整数，表示牛的重量和强壮程度，第i行表示第i头牛的重量Wi以及它的强壮程度Si。
输出格式
输出一个整数，表示最大风险值的最小可能值。
数据范围
1≤N≤50000,
1≤Wi≤10,000,
1≤Si≤1,000,000,000
输入样例：
3
10 3
2 5
3 3
输出样例：
2
(贪心)
思路: 与国王游戏的贪心策略相似， 我们先分析每头牛的危险值 = 他前面牛的w(重量值)和 - 自身的s(强壮值)，要使每头牛的危险值最小，这显然是与w 和 s同时相关，所以先 yy 出一种做法按 每头牛的w + s进行升序排序(题见多了可能就会有这种题感)。接下来进行数学分析证明:
牛 交换前 交换后
ii
∑j=1i−1wj−si
∑j=1i−1wj−si
∑j=1i−1wj+wi+1−si
∑j=1i−1wj+wi+1−si
i+1i+1
∑j=1iwj−si+1
∑j=1iwj−si+1
∑j=1i−1wj−si+1
∑j=1i−1wj−si+1
其他牛的危险值显然不变，所以分析交换前后这两头牛中最大的危险值即可。
将上述式子进行化简，每个式子减去 ∑i−1j=1wj∑j=1i−1wj得到如下式子
牛 交换前 交换后
ii
−si
−si
wi+1−si
wi+1−si
i+1i+1
wi−si+1
wi−si+1
−si+1
−si+1
由于s, w都是正数，wi−si+1>−si+1wi−si+1>−si+1 , wi+1−si>−siwi+1−si>−si
比较wi−si+1wi−si+1, wi+1−siwi+1−si即可
当wi−si+1>=wi+1−siwi−si+1>=wi+1−si，即 wi+si>=wi+1+si+1wi+si>=wi+1+si+1时, 交换后更优
当wi−si+1<wi+1−siwi−si+1<wi+1−si，即 wi+si<wi+1+si+1wi+si<wi+1+si+1时, 交换前更优
所以得到做法: 按每头牛的 w + s 进行排序, 当存在逆序时就进行交换(即升序排序)，
然后根据题意算出每头牛的危险值记录其中的最大值即可
代码:
#include #include using namespace std; typedef long long ll; typedef pair<int, int> PII; const int N = 5e4 + 5; PII a[N]; int main() { int n; cin >> n; for(int i = 0; i < n; i ++ ) { int x, y; scanf(“%d %d”, &x, &y); a[i].first = x + y; a[i].second = y; } sort(a, a + n); ll res = -1e18, sum = 0; for(int i = 0; i < n; i ++ ) { sum -= a[i].second; res = max(res, sum); sum += a[i].first; } cout << res << endl; return 0; }
底下的牛的强壮程度SS越大越好
上面牛的重量和WW越小越好(越重的放越下面)
=>
直觉是S[i]+W[i]越大的放越下面
证:
贪心得到的答案≥最优解(根据最优解定义:所有排序方案的最小值)
贪心得到的答案≤最优解
如果不是按S[i]+W[i]从小到大排序一定存在相邻i和i+1有wi+si>wi+1+si+1wi+si>wi+1+si+1
可以发现此时交换第ii头牛和第i+1i+1头牛不影响[0,i−1][0,i−1]和[i+2,n][i+2,n]的风险
变化 第ii个位置上的牛 第i+1i+1个位置上的牛
交换前
w1+…+w(i−1)−si
w1+…+w(i−1)−si
w1+…+w(i)−s(i+1)
w1+…+w(i)−s(i+1)
交换后
w1+…+w(i−1)−s(i+1)
w1+…+w(i−1)−s(i+1)
w1+…+w(i−1)+w(i+1)−s(i)
w1+…+w(i−1)+w(i+1)−s(i)
前i−1i−1项减去
变化 第ii个位置上的牛 第i+1i+1个位置上的牛
交换前
−si
−si
w(i)−s(i+1)
w(i)−s(i+1)
交换后
−s(i+1)
−s(i+1)
w(i+1)−s(i)
w(i+1)−s(i)
加上si+si+1si+si+1
变化 第ii个位置上的牛 第i+1i+1个位置上的牛
交换前
s(i+1)
s(i+1)
wi+si
wi+si
交换后
si
si
w(i+1)+s(i+1)
w(i+1)+s(i+1)
wi+si>siwi+si≥w(i+1)+s(i+1)wi+si≥max(si,w(i+1)+s(i+1))由wi+si>wi+1+si+1−>wi+si>si+1−>wi+si=max(s(i+1),wi+si)max(s(i+1),wi+si)≥max(si,w(i+1)+s(i+1))max(交换前)≥max(交换后)所有风险的最大值起码不会变大即只要wi+si不是严格递增,则我们可以把他们变成递增的并且所有风险的最大值不会变大
wi+si>siwi+si≥w(i+1)+s(i+1)wi+si≥max(si,w(i+1)+s(i+1))由wi+si>wi+1+si+1−>wi+si>si+1−>wi+si=max(s(i+1),wi+si)max(s(i+1),wi+si)≥max(si,w(i+1)+s(i+1))max(交换前)≥max(交换后)所有风险的最大值起码不会变大即只要wi+si不是严格递增,则我们可以把他们变成递增的并且所有风险的最大值不会变大
#include #include using namespace std; typedef pair<int,int> PII; const int N=50010; #define x first #define y second int n; PII cow[N]; int main() { cin >> n; for(int i=0;i<n;i++) { int w,s; cin >> w >> s; cow[i] = {w+s,w}; } sort(cow,cow+n); int res = -1e9,sum=0; for(int i=0;i<n;i++) { int s; s = cow[i].x-cow[i].y; res = max(res,sum-s);//风险 = 上面的重量-当前的承受 sum+=cow[i].y; } cout << res; return 0; }
