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

maple_tzc · 2018-02-04 16:53:38 · 题解

看了蛮多题解的，，发现一个惊人的事实，，代码玄学啊，，难懂，，
主要是太多高级的操作，，对我我等蒟蒻来说，，理解难度爆表；
所以，，特地来发了一波简单的代码，，
主要是贪心，，讲解其实楼下已经讲的很清楚了，
主要思想也就是找到每一头牛的相对价值最小，sort暴力排序一遍，，
接着就可以乱搞了，，（其实，，做到这一步了，，就差不多了可以直接将答案处理一下，加起来就好了）

贪心贪心
------------------------------------------------
********************************************
#include<cstdio>
#include<algorithm>
using namespace std;
int n,total;
long long ans;
struct data{
    int t,d;
}a[100001];
bool cmp(data a,data b){
    return min(a.t,b.d)<min(a.d,b.t);
}
int main()
{
    long long ans;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].t,&a[i].d);
    }
    sort(a+1,a+n+1,cmp);
    for (int i=1; i<=n; i++){
        a[i].t+=a[i-1].t;//前缀和，，，别告诉我这个你不会；
    }
    ans=a[1].t;
    for(int i=1;i<=n;i++)
    {
       if (a[i].t>ans)
       ans=a[i].t;
       ans+=a[i].d;
    }
    printf("%lld",ans);
    return 0;
}
************************************************