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

迈不过友情╰ 2021-11-05 07:02 228阅读 0赞

# [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  
![在这里插入图片描述][20190808173249499.gif]  
**Sample Output**  
4  
![在这里插入图片描述][20190808173304802.gif]

--------------------

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

那么问题就抽象为：由  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;
    }

[BZOJ 1113 _PLA]: https://www.lydsy.com/JudgeOnline/problem.php?id=1113
[20190808173249499.gif]: /images/20211104/463da16d60bb4be4a7bb85d2676fc7af.png
[20190808173304802.gif]: /images/20211104/8fad729ebdbc499493543a4a05bc75f6.png