BZOJ 1113 海报PLA——————单调栈

BZOJ 1113 海报PLA

Description
N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.

Input
第一行给出数字N,代表有N个矩形.N在[1,250000] 下面N行,每行给出矩形的长与宽.其值在[1,1000000000]2 1/2 Postering

Output
最少数量的海报数.

Sample Input
5

1 2

1 3

2 2

2 5

1 4
在这里插入图片描述
Sample Output
4

我们可以直接忽略长度，因为长度对这一道题的结果影响不大

那么问题就抽象为：由 n n n 个长度为 1 1 1 ，高度为 h 1 ， h 2 , . . . h n h_1， h_2, … h_n h1，h2,…hn 的长方形从左到右依次排列组成的柱状图，问里面包含的长方形的最少个数是多少

我们依旧维护一个单调递增栈，如果当前元素与栈顶元素相等，那么它就可以与栈顶元素在同一个矩阵里面

/*--------- Hongjie ----------*/
/**
 *　　　　　　　　┏┓　　　┏┓+ +
 *　　　　　　　┏┛┻━━━┛┻┓ + +
 *　　　　　　　┃　　　　　　　┃
 *　　　　　　　┃　　　━　　　┃ ++ + + +
 *　　　　　　 ████━████ ┃+
 *　　　　　　　┃　　　　　　　┃ +
 *　　　　　　　┃　　　┻　　　┃
 *　　　　　　　┃　　　　　　　┃ + +
 *　　　　　　　┗━┓　　　┏━┛
 *　　　　　　　　　┃　　　┃
 *　　　　　　　　　┃　　　┃ + + + +
 *　　　　　　　　　┃　　　┃　　　　Code is far away from bug with the animal protecting
 *　　　　　　　　　┃　　　┃ + 　　　　神兽保佑,代码无bug
 *　　　　　　　　　┃　　　┃
 *　　　　　　　　　┃　　　┃　　+
 *　　　　　　　　　┃　 　　┗━━━┓ + +
 *　　　　　　　　　┃ 　　　　　　　┣┓
 *　　　　　　　　　┃ 　　　　　　　┏┛
 *　　　　　　　　　┗┓┓┏━┳┓┏┛ + + + +
 *　　　　　　　　　　┃┫┫　┃┫┫
 *　　　　　　　　　　┗┻┛　┗┻┛+ + + +
 */
// #include<bits/stdc++.h>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int ,int> P;
const int INF  = 0x3f3f3f3f;
const int MAXN = 3e6+7;
int h[MAXN];
int main(){
        // freopen("../in.txt","r",stdin);
        // freopen("../out.txt","w",stdout);
        ios::sync_with_stdio(0);
        cin.tie(0);
        int n,x;
        while(cin>>n) {
                for(int i=0;i<n;++i) {
                        cin>>x>>h[i];
                }
                stack<int> s;
                int ans = n;
                for(int i=0;i<n;++i) {
                        while(!s.empty() && s.top() >= h[i]) {
                                if(h[i]==s.top()) //如果当前元素与栈顶元素相等，
                                        ans --;   //那么它就可以与栈顶元素在同一个矩阵里面
                                s.pop();
                        }
                        s.push(h[i]);
                }
                cout<<ans<<endl;
        }
        return 0;
}