描述
http://poj.org/problem?id=3045
n头牛,每头牛都有重量w[i]和力量s[i].把这n头牛落起来,每头牛会有一个危险值,危险值是它上面所有牛的重量和减去它的力量.求危险值最大的牛的危险值的最小值.
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 4102 | Accepted: 1569 |
Description
The cows aren't terribly creative and have only come up with one
acrobatic stunt: standing on top of each other to form a vertical stack
of some height. The cows are trying to figure out the order in which
they should arrange themselves ithin this stack.
Each of the N cows has an associated weight (1 <= W_i <=
10,000) and strength (1 <= S_i <= 1,000,000,000). The risk of a
cow collapsing is equal to the combined weight of all cows on top of her
(not including her own weight, of course) minus her strength (so that a
stronger cow has a lower risk). Your task is to determine an ordering
of the cows that minimizes the greatest risk of collapse for any of the
cows.
Input
* Lines 2..N+1: Line i+1 describes cow i with two space-separated integers, W_i and S_i.
Output
Sample Input
3
10 3
2 5
3 3
Sample Output
2
Hint
Put the cow with weight 10 on the bottom. She will carry the other
two cows, so the risk of her collapsing is 2+3-3=2. The other cows have
lower risk of collapsing.
Source
分析
贪心.
易证:w+s越大应在越下面(又重,又有力气,当然放在下面...).
所以排序,扫一遍即可.
注意:
1.ans的初始值应为-INF而非0,因为很可能大家的力气都很大,但都很轻!
#include<cstdio>
#include<algorithm>
using std :: sort;
using std :: max; const int maxn=,INF=0x7fffffff;
int n; struct point
{
int w,s,sum;
}c[maxn]; bool comp(point x,point y) { return x.sum<y.sum; } void solve()
{
sort(c+,c+n+,comp);
int ans=-INF,sum=;
for(int i=;i<=n;i++)
{
ans=max(ans,sum-c[i].s);
sum+=c[i].w;
}
printf("%d\n",ans);
} void init()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&c[i].w,&c[i].s);
c[i].sum=c[i].w+c[i].s;
}
} int main()
{
freopen("cow.in","r",stdin);
freopen("cow.out","w",stdout);
init();
solve();
fclose(stdin);
fclose(stdout);
return ;
}