P3467 PLA-Postering 题解

· · 题解

可能更好的食用体验 | 题目传送门 | 我的其他题解

{\color{SkyBlue}\mathtt{Analysis}}

5
1 2
1 3
2 2
2 5
1 4

(上图为题目样例的海报摆法。)

由此，我们可以发现：其实就是一层一层的摆，如果这个高度在之前已经出现，那么当前建筑就不需要增添一张海报。（其实第一个值 d_i 是没什么用的 ，只是在题目中用来描述位置的。）

{\color{SkyBlue}\mathtt{Ideas}}

那么，这就是典型的 维护单调队列（栈） 的题啦！

可以通过分析题目来得出答案：

如果是单调下降，那么这张海报则可能把更矮的建筑上方的空白也覆盖掉，那么就违背了题意！！

由此可知，本题需要维护的是单调上升序列。

如果还不会单调队列，那么就应该先去学习一下这道模板题

{\color{SkyBlue}\mathtt{Code}}

#include<iostream>
#include<cmath>
#include<cstdio>
#include<stack>
using namespace std;
stack<int> t;
int n,p,a,ans=0;
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d %d",&p,&a);
        while(!t.empty() && t.top()>a) 
            t.pop();
        //弹出比a大的数，从而保证a进栈后t仍旧单调上升。
        if(t.empty() || t.top()!=a)
            ans++,t.push(a);
    }
    printf("%d",ans);
    return 0;
}

说明：By Xin。本人乃2016级小学生，思路比较简单，题解如有写的不好的地方请指正，谢谢。