Codeforces Round #401 (Div. 2) E. Hanoi Factory（贪心 + 单调栈）

E. Hanoi Factory

题意：

给你$n$个汉诺塔，每个汉诺塔有三个数$a$,$b$,$h$，分别代表内径，外径，和高。现在让你将这$n$个汉诺塔根据以下规则叠加起来，使其的总高最高。
规则：

1. 已经放好的汉诺塔的外径$b$要符合非递增，如$bi>bj$，这样$j$才有可能叠加到i上。
2. $ai<bj$，同时满足1,2规则才能将$j$叠放到$i$上。

题解：

贪心 + 单调栈

1. 我们将单调栈看着做已经叠加好的汉诺塔。
2. 我们先将$b$从大到小排列，若$b$相同，则按$a$从大到小排列。我们来重点解释一下为什么$a$从大小排列??
   我们排完序后$b$是从大到小，约往后叠加$b$越小，若想要满足规则2，我们栈顶的$ai$要比$bj$小，所以我们贪心将a从大到小排序，这样就会使得栈顶上的$a$尽可能小。
3. 剩下就是单调栈的操作了，若栈顶的不满足规则2，则将它pop，知道符合规则2。

ACcode

/** @Author: NEFU_马家沟老三* @LastEditTime: 2020-09-30 20:56:19* @CSDN blog: https://blog.csdn.net/acm_durante* @E-mail: 1055323152@qq.com* @ProbTitle: */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define lowbit(x) ((x) & -(x))
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define mem(a, b) memset(a, b, sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
ll powmod(ll a,ll b) {
    ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){
    if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) {
     return b?gcd(b,a%b):a;}
template<class T>inline void read(T &res)
{
    
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
const int N = 1e5+5;
struct node
{
    int a,b;ll h;bool operator < (const node &x)const{
    if(b != x.b)//第一元素递减return  b > x.b; return   a > x.a;//第二元素递减}
}e[N];
int n;
int s[N];//手工模拟单调栈
ll solve(int n){
    ll res = 0,ans = 0;int cnt = 0;rep(i,1,n){
    if(cnt == 0){
    //栈为空，则需要进栈res += e[i].h;s[++cnt] = i;}  else{
    if(e[ s[cnt] ].a < e[i].b){
    //符合规则2，进栈res += e[i].h;s[++cnt] = i;}else{
    while(e[ s[cnt] ].a >= e[i].b && cnt !=0){
    //不符合规则2，则出栈，直到符合规则2。res-=e[ s[cnt] ].h;--cnt;}s[++cnt] = i;res += e[i].h; }}ans = max(ans,res);//每次记录下最大值}return ans;
}int main()
{
    IOScin >> n;rep(i,1,n) cin >> e[i].a >> e[i].b >> e[i].h;sort(e+1,e+1+n);cout << solve(n) << "\n";return 0;
}