题目：P3467 [POI 2008] PLA-Postering

题目描述

Byteburg 城市的东区所有建筑都是按照旧式建筑风格建造的：它们一个接一个地紧挨在一起，中间没有任何间隔。它们从东到西排列，形成了一排高度各异的建筑长廊。

Byteburg 的市长 Byteasar 决定在这排建筑的北立面上张贴海报。他正在思考，要完全覆盖整个北立面，最少需要多少张矩形海报。这些海报的边是垂直或水平的矩形，不能重叠，但可以相接（即边缘可以重合）。每一张海报必须完全贴合某些建筑的墙面，且所有北立面必须被完全覆盖。

你的任务是写一个程序，完成以下功能：

• 从标准输入中读取建筑的描述，
• 计算出最少需要多少张海报，才能完全覆盖建筑的北立面，
• 将结果输出到标准输出。

输入格式

标准输入的第一行包含一个整数 $n$（$1\le n\le 250000$），表示这一排建筑的数量。

接下来的 $n$ 行中，每行包含两个整数 $d_i$ 和 $w_i$（$1\le d_i,w_i\le 1000000000$），分别表示第 $i$ 栋建筑的宽度和高度。

输出格式

标准输出中输出一个整数，表示最少需要多少张矩形海报，才能完全覆盖建筑的北立面。

输入输出样例 #1

输入 #1

5
1 2
1 3
2 2
2 5
1 4

输出 #1

4

说明/提示

代码

#include<iostream>using namespace std;const int Maxn = 250000 + 10;int n, st[Maxn], tt, h[Maxn], sum;void insert(int x){st[++ tt] = x;
}void dele(){tt --;
}bool isempty(){return tt <= 0;
}int main(){cin >> n;for(int i = 1; i <= n; i ++){int w;cin >> w >> h[i];while(!isempty() && h[i] < h[st[tt]]){dele();}if(isempty() || h[i] != h[st[tt]]){sum ++;}insert(i);}cout << sum;return 0;
}

结果