[CF777E] Hanoi Factory（贪心，栈）

题目链接：http://codeforces.com/problemset/problem/777/E

外环从大到小，内环从大到小排序。用一个栈来存当前待选择做底盘的环。遍历每一个环，找到第一个内环符合条件的栈中环，更新当前遍历到的环的高度，放入栈。更新答案即可。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef struct P {
    LL a, b, h;
    P() {}
    P(LL a, LL b, LL h) : a(a), b(b), h(h) {}
}P;
const LL maxn = 100100;
LL n;
P p[maxn];

bool cmp(P x, P y) {
    if(x.b == y.b) return x.a > y.a;
    return x.b > y.b;
}
stack<P> st;

signed main() {
    // freopen("in", "r", stdin);
    while(~scanf("%I64d", &n)) {
        for(LL i = 1; i <= n; i++) {
            scanf("%I64d%I64d%I64d",&p[i].a,&p[i].b,&p[i].h);
        }
        sort(p+1, p+n+1, cmp);
        while(!st.empty()) st.pop();
        LL ret = 0;
        for(LL i = 1; i <= n; i++) {
            while(!st.empty() && p[i].b <= st.top().a) st.pop();
            if(!st.empty()) p[i].h += st.top().h;
            st.push(p[i]);
            ret = max(ret, st.top().h);
        }
        printf("%I64d
", ret);
    }
    return 0;
}