poj 3045 Cow Acrobats(数学题)

题目链接：http://poj.org/problem?id=3045

Description

Input

Output

Sample Input

3
10 3
2 5
3 3

Sample Output

2

Hint

Source

题意：这道题居然和今年成都赛区的倒数第二题一模一样。。。或者说该反过来说、、给你n头牛叠罗汉，每头都有自己的重量w和力量s，承受的风险数就是该牛上面牛的总重量减去它的力量，题目要求设计一个方案使得所有牛里面风险最大的要最小。

题解：按照w+s贪心叠，越大的越在下面。如果最优放置时，相邻两头牛属性分别为w1,s1,w2,s2,第一头牛在第二头上面，sum为第一头牛上面的牛的体重之和，那么

第一头牛风险：a=sum-s1;第二头牛风险:b=sum+w1-s2;交换两头牛位置之后

a‘=sum+w2-s1,b‘=sum-s2，

由于是最优放置，所以w2-s1>=w1-s2，即w2+s2>=w1+s1，所以和最大的就该老实的在下面呆着= =！

以上转载！

思路：

先按照w+s的和的大小排序，大的在下面，最后在把过程中最大的危险值求出来！

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 50017;
#define INF 0x3f3f3f3f
typedef struct
{
    int w, s;
    int ss;
} COW;
COW cow[MAXN];
bool cmp(COW a, COW b)
{
    return a.ss < b.ss;
}
int main()
{
    int n;
    int sum[MAXN];
    while(~scanf("%d",&n))
    {
        memset(sum,0,sizeof(sum));
        for(int i = 1; i <= n; i++)
        {
            scanf("%d%d",&cow[i].w,&cow[i].s);
            cow[i].ss = cow[i].w+cow[i].s;
        }
        sort(cow+1,cow+n+1,cmp);
        int ans = -INF;
        for(int i = 1; i <= n; i++)
        {
            sum[i] = sum[i-1]+cow[i].w;
            ans = max(ans,sum[i-1]-cow[i].s);
        }
        printf("%d\n",ans);
    }
    return 0;
}

poj 3045 Cow Acrobats(数学题)

原文：http://blog.csdn.net/u012860063/article/details/39229321