题目链接

http://codeforces.com/contest/777/problem/E

题目大意

有一个类似于汉诺塔的游戏，只是每个圆盘中间都是空心的，一个环 $i$ 能放在另一个环 $j$ 上当且仅当它的外半径小于 $j$ 环的外半径且外半径大于 $j$ 环的内半径，否则它将掉下去。现在已知每个环的高度，需要你求出最高能摆多高。

题目分析

这题注意到一个性质，如果对于一个环 $i$ ，它因为外半径过小无法放到圆环 $j$ 上，那么所有外半径小于等于 $i$ 的均无法放到圆环 $j$ 上。那么可以贪心求解。先将所有的圆环按外半径大小从大到小排序，如果外半径相同则按内半径大小从大到小排序，用栈来维护当前已经搭好的汉诺塔部分，每放进一个新的圆盘，将栈顶所有无法放它的圆盘全部弹出，记录高度，取最大值即可

时间复杂度： $O(N \times \log_{2}{N})$

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

int n;

struct ex {
    long long a;
    long long b;
    long long h;
};

struct sta {
    long long h[100005];
    long long a[100005];
    int p;
    
    long long topa(){
        return a[p];
    }
    
    long long toph(){
        return h[p];
    }
    
    int push(long long t, long long ht){
        p++;
        a[p] = t;
        h[p] = h[p - 1] + ht;
        return 0;
    }
    
    int pop(){
        p--;
        return 0;
    }
    
    sta(){p = 0;h[0] = 0;a[0] = 0;};
};

ex ring[100005];

sta s;

long long maxh = 0;

bool cmp(ex a, ex b){
    if(a.b != b.b){
        return a.b > b.b;
    }else{
        return a.a > b.a;
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    
    int i, j;
    
    cin >> n;
    
    for(i=1;i<=n;i++){
        cin >> ring[i].a;
        cin >> ring[i].b;
        cin >> ring[i].h;
    }
    
    sort(ring + 1, ring + n + 1, cmp);
    
    for(i=1;i<=n;i++){
        while(ring[i].b <= s.topa()){
            s.pop();
        }
        s.push(ring[i].a, ring[i].h);
        maxh = max(maxh, s.toph());
    }
    
    cout << maxh << endl;
    
    return 0;
}