题目描述
农民约翰的 N 头奶牛(编号为 1..N)计划逃跑并加入马戏团,为此它们决定练习表演杂技。
奶牛们不是非常有创意,只提出了一个杂技表演:
叠罗汉,表演时,奶牛们站在彼此的身上,形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。
一头牛支撑不住的可能性取决于它头上所有牛的总重量(不包括它自己)减去它的身体强壮程度的值,现在称该数值为风险值,风险值越大,这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序,使得所有奶牛的风险值中的最大值尽可能的小。
样例
输入样例:
3
10 3
2 5
3 3
输出样例:
2
贪心算法
按s+w的和按从小到大排序
反证法
证明:
- 若存在
si+wi>s(i+1)+w(i+1)
由于si+wi>s(i+1)+w(i+1)
则wi+si>w(i+1)+s(i+1)
且wi+si>s
所以wi+si
必然大于交换后的两项的最大值
所以交换前的最大值必然大于交换后的最大值,也就是说交换后答案变小了,故该算噶是对的
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=50010;
PII cnt[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int s,w;
scanf("%d%d",&w,&s);
cnt[i]={w+s,s};
}
sort(cnt,cnt+n);
int res=-2e9,sum=0;
for(int i=0;i<n;i++)
{
int s=cnt[i].second,w=cnt[i].first-s;
res=max(res,sum-s);
sum+=w;
}
cout<<res<<endl;
return 0;
}