题目描述
农民约翰的 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
算法1
贪心问题关键是要找准贪心策略,这种每个物体有两个属性,
且按照一定顺序排列的贪心题目可行的方案之一如下:
对于这种贪心问题满足在最优解的基础上交换顺序后特定的解
会发生改变(同样类型的题目还有洛谷p1080国王游戏);那么我们
根据这一特性来进行贪心推导,本题推导如下:
首先对于任意两条牛a,b;
能够交换a,b两条牛的位置的必要条件是其中一条牛放在上面使得最大值
最小,下面分情况讨论:
1、a牛放在b牛的上面
此时a牛的风险值f1=Wn-Sa,b牛的风险值为f2=Wn+Wa-Sb;
2、b牛放在a牛的上面
此时a牛的风险值f3=Wn+Wb-Sa,b牛的风险值为f4=Wn-Sb;
接下来我们要比较的是max(f1,f2),max(f3,f4)的大小;
很明显我们可以发现因为w>=1所以f4<f2,f1<f3;(1)
假设max(f1,f2)>max(f3,f4);(2)
据(1)(2)可得f2>f1;(3)
据(3)得f2>f3 解得Wa+Sa>Wb+Sb;
又因为(2)为a牛在b牛上且最大值最大,
所以a牛在b牛上且最大值最小就应该是Wa+Sa<=Wb+Sb;
当max(f1,f2)<=max(f3,f4)时推导同上
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=50010;
struct cow
{
int w,s;
}a[N];
bool cmp(cow a,cow b)
{
return (a.s+a.w)<(b.s+b.w);
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int c,b;
cin>>c>>b;
a[i]={c,b};
}
sort(a,a+n,cmp);
int res=-1e8;
int sum=0;
for(int i=0;i<n;i++)
{
int x=sum-a[i].s;
res=max(res,x);
sum+=a[i].w;
}
cout<<res<<endl;
}