题意描述

Byteburg市东边的建筑都是以旧结构形式建造的。

建筑互相紧挨着,之间没有空间。

它们共同形成了一条长长的,从东向西延伸的建筑物链(建筑物的高度不一)。

Byteburg市的市长Byteasar,决定将这个建筑物链的一侧用海报覆盖住.并且想用最少的海报数量。

海报是矩形的。海报与海报之间不能重叠,但是可以相互挨着(即它们具有公共边)。

每一个海报都必须贴近墙并且建筑物链的整个一侧必须被覆盖，即海报需要将一侧全部覆盖,并且不能超出建筑物链)

现在，请您编写程序帮助计算，并输出最少需要用的海报数量。

输入格式

第一行为一个整数$n$,表示有$n$个建筑。

接下来$n$行中,第$i$行表示第$i$个建筑物的宽$d_i$与高$w_i$，中间由一个空格隔开。

输出格式

输出仅有一行，为一个整数,表示最少需要的海报数量.

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围与约定

对于$100\%$的数据，保证有$1≤n≤2.5 \times 10^5 , 1≤d_i,w_i≤10^9$

分析

单调栈入门经典必做题。

考虑所有建筑都一样高时的做法。很显然，当所有建筑高度一致时，我们仅需要一张海报即可覆盖所有的建筑。

再考虑最坏情况的答案。最坏的做法也就是每一个建筑上都挂一张海报，这时的答案为$n$。也就是说，我们的答案一定不会超过$n$。

考虑如何减少海报数量。

不难发现，若有两个不等高的建筑物，则我们所需的海报数量至少为$2$张。

而如果有一个建筑物，它左右的建筑物都比他低，则可以省下一张海报

因此我们可以维护一个单调栈，若栈顶高度大于当前入栈的元素，则弹栈，若等于，则将需要的海报数$-1$。直到小于为止。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline

using namespace std;


ll n , k , l;
ll ans;
stack<ll > S;

int main(){
    cin >> n;
    ans = n;
    S.push(-0x3f3f3f3f);    //防止非法访问
    cin >> k >> l;
    S.push(l);
    for(int i = 2; i <= n; i ++){
        cin >> k >> l;
        while(S.top() >= l){
            if(S.top() == l){
                ans --;
            }
            S.pop();
        }
        S.push(l);
    }
    cout << ans << "\n";
    return 0;
}