题目:耍杂技的牛
题意:
农民约翰的 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
思路:
-
排序方式: 将n头牛按照
w[i]+s[i]
从小到大排序。 -
证明: 假如最优解中存在
w[i]+s[i]>w[i+1]+s[i+1]
(这里的下标指牛在最优解中的位置,不是输入时的下标),那么交换两头牛的位置可以得到
第i个位置上的牛 第i+1个位置上的牛
交换前 w[1]+w[2]+...w[i-1]-s[i] w[1]+w[2]+...w[i-1]+w[i]-s[i+1]
交换后 w[1]+w[2]+...w[i-1]-s[i+1] w[1]+w[2]+...w[i-1]+w[i+1]-s[i]
四项同时减去 `w[1]+w[2]+...w[i-1]` 并加上 `s[i]+s[i+1]` 可以得到
交换前 s[i+1] w[i]+s[i]
交换后 s[i] w[i+1]+s[i+1]
- 因为牛的体重和强壮值都是正数,所以
w[i]+s[i]>s[i]
,又因为最优解存在w[i]+s[i]>w[i+1]+s[i+1]
,所以可以发现这四项的最大值不在交换后这两项中,从而得到两头牛交换位置后最大的风险值减小。而对于最优解中的任何两头牛都可以通过这样的方式交换两头牛的位置,所以根据w[i]+s[i]
排序是最优的。
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=50010;
#define PII pair<int,int>
int n;
PII p[N];
bool cmp1(PII a,PII b)
{
return a.first+a.second<b.first+b.second;
}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)cin>>p[i].first>>p[i].second;
sort(p+1,p+n+1,cmp1);
int sum=0,mm=-0x3f3f3f3f;
for(int i=1;i<=n;++i)
{
mm=max(mm,sum-p[i].second);
sum+=p[i].first;
}
cout<<mm;
return 0;
}