题解 P1561 【[USACO12JAN]爬山Mountain Climbing】

Kirin · 2018-01-01 15:31:58 · 题解

被叫去给学弟讲这道题，没想到被学弟Hack了。。。Orz

做法和大家一样：

ans=\max\left\{\sum_{k=1}^n{up_k}+down_{\min},\sum_{k=1}^n{down_k}+up_{\min}\right\}

但是这个做法是不完全正确的，比如以下数据：

正确答案应该是18而不是17，这个可以手动模拟，会发现之前的做法有问题。

我去查了一下USACO官方题解，下面来简单说一下。

首先，贪心的想法和之前的做法是相同的，就是让更多的牛早到山顶；
我们把牛分成两类：1. up < down 2. up > down，up=down的归为任意一类是不影响的；
之后，考虑到up小的先到山顶不会拖慢后面的牛，我们把第一类都排在第二类前面，而且按up升序排；
第二类牛我们按down降序排，这个没上面那个显然，但是原因也很简单，下的慢的先下可以拖住后面的牛下山，减少出现山顶的牛已经下完了，下面的牛还没上完这种浪费的情况；
之后是计算时间，其实最初那个方法的贪心策略和上面应该是相同的，但是计算出了问题；
那组数据之所以被Hack，就是因为最初的方法认为第一个牛上山后，所有上下山是一起进行的，其实有可能出现不重叠的情况，于是少算了；
正确的做法是按之前那个策略排序后，O(n)模拟一下。

代码：

#include <cstdio>
#include <algorithm>

using std::sort;
using std::max;

const int MAXN=25005;
int n;
int up_tm[MAXN],dwn_tm[MAXN];

struct Cow{
    int up,dwn;
    static bool cmp_tm(const Cow &a,const Cow &b){
        if(a.up<a.dwn){
            if(b.up<b.dwn) return a.up<b.up;
            else return true;
        }
        else{
            if(b.up<b.dwn) return false;
            else return a.dwn>b.dwn;
        }
    }
}cow[MAXN];

inline int greedy(){
    sort(cow+1,cow+n+1,Cow::cmp_tm);
    for(int i=1;i<=n;++i)
        up_tm[i]=up_tm[i-1]+cow[i].up;
    for(int i=1;i<=n;++i)
        dwn_tm[i]=max(dwn_tm[i-1],up_tm[i])+cow[i].dwn;
    return dwn_tm[n];
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&cow[i].up,&cow[i].dwn);
    printf("%d",greedy());
    return 0;
}