题目描述
农民约翰的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
思路
交换前 交换后
第i头牛 w1+w2+...+wi-1 - si w1+w2+...+wi+1 - si
第i+1头牛 w1+w2+...+wi - si+1 w1+w2+...+wi-1 - si+1
每一项都有 w1+w2+...+wi-1
————————————————————————————————————————
可以转换为
交换前 交换后
第i头牛 - si wi+1 - si
第i+1头牛 wi - si+1 - si+1
————————————————————————————————————————
易知 -si < wi+1-si
wi- si+1 > -si+1
所以判断wi+1-si 和 wi-si+1 的关系
wi - si+1 > wi+1 - si
==> wi + si > wi+1 + si+1
所以只要满足 wi + si > wi+1 + si+1 ,即可满足交换前的两个数字的最大值必定大于交换后的两个数字的最大值
即max( - si , wi - si+1 ) > max( wi+1 - si , - si+1)
得出结论当 wi + si > wi+1 + si+1 时,交换两头牛,可以降低最大风险值
要想风险值最小,就要满足wi + si < wi+1 + si+1 , 即后一头牛的 wi+si 要大于前一头牛,因此按照从小到大进
行排序
每次更新这头牛头上的重量,减去自身的强壮度,更新前i头牛的最大风险值
C++ 代码
#include<iostream>
#include<algorithm>
#include<limits.h>//含INT_MIN
using namespace std;
const int N=5e4+5;
struct node{
int w; //重量
int s; //强壮程度
}a[N];
int n;
bool cmp(node a,node b){//按照重量和强壮程度之和从小到大排序
return a.w+a.s<b.w+b.s;
}
int main()
{
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i].w >> a[i].s;
}
sort(a+1,a+1+n,cmp);//从小到大排序
int sum=0;//sum即为当前第i头牛的风险值
int res=INT_MIN;//初始值为最小值,要加头文件 #include<limits.h>
for(int i=1;i<=n;i++){
res=max(res,sum-a[i].s);//res为前i头牛的最大风险值,不断更新
sum=sum+a[i].w;//更新下一头牛头上总共的重量
}
cout << res << endl;
return 0;
}