P3467 贴海报

本文主要是介绍P3467 贴海报，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

纯单调栈结构。海报的最大数量为建筑个数，而如果在一个峰/等高的两侧有两个高度相等的建筑则答案减一。用单调栈维护一个不降序列，若进栈元素小于栈顶元素，则不断弹出栈顶，元素入栈后若栈顶与次栈顶相等则答案减一。

#include<iostream>
#include<algorithm>
#define MAXN 250007
using namespace std;
int rub, val, st[MAXN], top, ans, n;
int main(void)
{
    cin >> n;
    ans = n;
    for (int i = 1; i <= n; i++)
    {
        cin >> rub >> val;
        while (top > 0 && st[top] > val)
            top--;
        st[++top] = val;
        if (st[top] == st[top - 1])
            ans--;
    }
    cout << ans;
    return 0;
}

这篇关于P3467 贴海报的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！