耍杂技的牛
农民约翰的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
C++ 代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
/*
由题意,使得整个系统中的 风险值最大的环节 的风险值最小。
又因为对于任一环节,风险值计算方式相同。得到普适风险值描述:
按序号排列时 (i+1)环节 的风险值:
Risk_1: sum{w0 + w1 + ... + wi} - S_{i+1}
牛i 和 牛i+1 互换后的风险值:
Risk_2: sum{w0 + w1 + ... + w_{i+1}} - Si
欲使得风险值变小,Risk_2 - Risk_1 > 0,一定有
W(i+1) + S(i+1) > W(i) + S(i)
重要思维:
1. 对任意一个环节分析风险值的思维。借此可以抽象为数学模型。
2. 前 i 个元素互换的思维,即交换验证思维。
交换验证方式 在应用到 整个堆叠 中显然是成立的;
由于范围确定,且简化模型的分析方法(从二牛开始)显示从前向后分析可行,
由此而得。
3. 复合数据的排序处理。sort函数,cmp对应情况置1,作为第三个参数;
*/
typedef long long LL;
typedef pair<int, int> PII;
#define w first
#define s second
const int CNT = 50000;
PII cows[CNT + 5];
// 期望 升序or降序 就设置对应的返回值为 1;
bool cmp(PII a, PII b) {
return (a.w + a.s) < (b.w + b.s);
}
int main() {
int n;
cin >> n;
memset(cows, 0, sizeof(cows));
for (int i = 1; i <= n; i++) {
scanf("%d%d", &cows[i].w, &cows[i].s);
}
// 排序 得到理想的 堆叠方式。
sort(cows + 1, cows + n + 1, cmp);
// 最大风险值;
LL wSum = 0;
int rsk = wSum - cows[1].s - 1;
// 基于已有的堆叠信息进行更新;
for (int i = 1; i <= n; i++) {
// 更新为最大值;
rsk = max(rsk, (int)wSum - cows[i].s);
wSum += cows[i].w;
}
cout << rsk << endl;
return 0;
}