Codeforces 777E：Hanoi Factory

Codeforces 776E：Hanoi Factory

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

题目大意：给出$n$个圆环，每个圆环有内径$a_i$，外径$b_i$，高$h_i$。圆环$x$能放在圆环$y$上仅当$a_y < b_x leqslant b_y$，问这些圆环最多能搭多高。

贪心

首先对所有圆环按外径从大到小（外径小的要放外径大的上面）内径从大到小（相同外径的情况下，显然将内径越小的防越上面更有利后面圆环的放置）排序.

从最上面（外径最小）开始考虑，由于已经按照外径降序排列（满足$b_x leqslant b_y$），故$x$能否放在$y$上仅与$a_y < b_x$是否成立有关.

若$x$能放在$y$上，则可将$x$与$y$合并（$b_x leqslant b_y$，若$y$不能放在下一个$z$上，$x$必然不能放在$z$上；且$y$是否能放在$z$上只与$b_y$的大小有关）；

若$x$不能放在$y$上，则可将$x$存入栈中（这样保证了后入栈的外径比先入栈的大），当$y$能放在下一个$z$上时再检验栈中$x$能否能放在$z$上，若$x$能放在$z$上则取$h$较大的与$z$合并（因为$z$是否能放在下一个上只与$b_z$的大小有关）.

/*注意此题会爆int*/

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <stack>
 5 using namespace std;
 6 typedef long long ll;
 7 int n;
 8 struct node{
 9     ll x,y,h;
10     bool operator < (node b)const{
11         if(x==b.x)return y>b.y;
12         return x>b.x;
13     }
14 }a[100005];
15 stack<pair<ll,ll> >s;
16 int main(void){
17     std::ios::sync_with_stdio(false);
18     cin>>n;
19     for(int i=0;i<n;++i)
20         cin>>a[i].y>>a[i].x>>a[i].h;
21     sort(a,a+n);
22     ll r=a[n-1].x,h=a[n-1].h,ans=a[n-1].h;
23     for(int i=n-2;i>=0;i--){
24         if(r>a[i].y){
25             r=a[i].x;
26             h+=a[i].h;
27             pair<ll,ll> t;
28             while(!s.empty()){
29                 t=s.top();
30                 if(t.first>a[i].y){
31                     s.pop();
32                     h=max(h,t.second+a[i].h);
33                 }else break;
34             }
35         }else{
36             s.push(make_pair(r,h));
37             r=a[i].x;
38             h=a[i].h;
39         }
40         ans=max(ans,h);
41     }
42     cout<<ans;
43 }