传送门
纯单调栈结构。海报的最大数量为建筑个数,而如果在一个峰/等高的两侧有两个高度相等的建筑则答案减一。用单调栈维护一个不降序列,若进栈元素小于栈顶元素,则不断弹出栈顶,元素入栈后若栈顶与次栈顶相等则答案减一。
#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; }