111qqz的小窝

老年咸鱼冲锋!

BZOJ 1628: [Usaco2007 Demo]City skyline (单调栈)

1628: [Usaco2007 Demo]City skyline

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 396  Solved: 317
[Submit][Status][Discuss]

Description

Input

第一行给出N,W
第二行到第N+1行:每行给出二个整数x,y,输入的x严格递增,并且第一个x总是1

Output

输出一个整数,表示城市中最少包含的建筑物数量

Sample Input

10 26
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1

INPUT DETAILS:

The case mentioned above

Sample Output

6
思路:我是正着做的,判断条件没有问题,但是细节不好处理,一直WA..大概是有什么地方没想到? 正解是单调栈。
转载一段题解:

答案的上限 肯定是 n, 何时会减一呢? 当有两座楼高度相等且它们的中间没有比它们低的楼。

所以要维护的是一个单调递增的序列, 每次弹出比它大的直到遇到一个和它相等的, 没有相等的话就把 它加入这个序列中。

实现很简单。

说点什么

您将是第一位评论人!

提醒
wpDiscuz