自动搬运

查看原文

来自洛谷，原作者为

	Kirin **

搬运于2025-08-24 21:26:29，当前版本为作者最后更新于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\} $$

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

3
6 4
8 3
2 1

正确答案应该是$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;
}