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

jzqjzq · 2017-02-12 10:53:34 · 题解

一个比较巧妙的贪心。和楼下做得不一样。

我们可以证明，本题的最优解即为max（总上山时间+最快奶牛下山时间，总下山时间+最快奶牛上山时间）

首先我们可以知道，当上山总时间大于下山总时间时，所有奶牛总上山时间恒定。

而最后总有一只奶牛在上山总时间后在山顶，要想最优，只要让在山上的那只奶牛下山时间最小即可。

下山同理，当上山总时间小于下山总时间时，所有奶牛总下山时间恒定。

在下山之前，总有一只奶牛在山顶（否则他还没上山就下山可能吗），要想最优，只要让在山上的那只奶牛上山时间最小即可

边读边做，每次读入累加上山和下山时间和记录最小上山下山时间最后去max即可

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
const int oo=100000000;
int n,p,q,pp,qq,a,b;
int main()
{
    cin>>n;
    pp=qq=oo;//赋初值
    p=q=0;//赋初值
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        p+=a;q+=b;//累加时间
        if(a<pp)pp=a;//记录最快奶牛上山时间
        if(b<qq)qq=b;//记录最快奶牛下山时间
    }
    if(p+qq>q+pp)cout<<p+qq;//取两者中较大的输出
    else cout<<q+pp;
    return 0;
}