P3467. PLA-Postering

发表于 分类于 阅读次数： Waline： 本文字数： 172 阅读时长 ≈ 1 分钟

考点

  • 单调栈

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 50;
int n, ans, top, st[maxn];

int main() {
  int nul, x;
  cin >> n;
  while (n--) {
    cin >> nul >> x;
    while (top && x <= st[top]) {
      if (x != st[top]) ++ans;
      --top;
    }
    st[++top] = x;
  }
  while (top--) ++ans;
  cout << ans;
  return 0;
}

思路

本题宽度是没用的，因为海报能无限大。

作图发现，用单调栈维护一个高度单调递增序列；

当某高度h破坏单调性时，单调栈内大于等于h都要弹出，但只需计数大于h的高度；

不统计等于h的高度，是因为h原本就需要入栈，入栈后肯定会被某一次操作再次计数的。