BZOJ 1628: [Usaco2007 Demo]City skyline && BZOJ 1683双倍经验233333333

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

HINT

Source

单调栈,维护一个单调递增的栈,如果两边高度一样就把答案-1

#include<stack>
#include<cstdio>
using namespace std;
stack<int> a;
int n,w,ans;
int main(){
	scanf("%d%d",&n,&w);
	a.push(0);
	ans = n;
	for(int i=1;i<=n;i++){
		int c,b;
		scanf("%d%d",&c,&b);
		while (b<a.top()) a.pop();
		if(b==a.top())ans--;
		else a.push(b);
	}
	printf("%d",ans);
}

 

此条目发表在BZOJ, USACO, 其他, 单调栈分类目录。将固定链接加入收藏夹。