【POJ - 3045】Cow Acrobats （贪心）

佚名 5年前 (2019-08-04) 算法 1730人围观抢沙发百度已收录

Cow Acrobats

Descriptions

农夫的N只牛(1<=n<=50,000)决定练习特技表演。特技表演如下:站在对方的头顶上，形成一个垂直的高度。每头牛都有重量(1 <= W_i <= 10,000)和力量(1 <= S_i <= 1,000,000,000)。奶牛崩溃的风险等同于她身上所有的奶牛的重量(当然不包括她自己)减去她的力量。你的任务是确定奶牛的顺序，从而使得所有牛的风险中最大的一个尽量小。Input第1行：一个整数N 第2 . .N+ 1行: 两个空格分隔的整数重量wi和力量si来描述奶牛i。Output一个整数，在所有牛的风险中最大的一个

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Sample Input

Sample Output

Hint

样例解释: 把重量为10的牛放在底部。她将携带另外两只牛，所以她的崩溃的风险是2 +3-3= 2。其他的奶牛有比她低的崩溃风险。

题目链接

https://vjudge.net/problem/POJ-3045

简单想了一下用贪心w+s越大应在越下面(又重,又有力气,当然放在下面)

所以排序,扫一遍即可

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 100000+100
using namespace std;
int n;
struct node
{
    int w,s,sum;
    bool operator<(const node &c)const//按体重从小到大排序
    {
        return sum<c.sum;
    }
};
node a[Maxn];
int main()
{
    while(cin>>n)
    {
        for(int i=0;i<n;i++)
        {
            cin>>a[i].w>>a[i].s;
            a[i].sum=a[i].w+a[i].s;
        }
        sort(a,a+n);//排序
        int ans=-INF;//注意不能是0
        int sum=0;//累计体重
        for(int i=0;i<n;i++)
        {
            ans=max(ans,sum-a[i].s);//求最大的崩溃值
            sum+=a[i].w;//把上面的体重加一起
        }
        cout<<ans<<endl;
    }
    return 0;
}