BZOJ_1628_[Usaco2007_Demo]_City_skyline_(单调栈)

描述


http://www.lydsy.com/JudgeOnline/problem.php?id=1628

给出\(n\)个距形的影子,问最少是多少个建筑的?(建筑的影子可以重叠).

分析


用单调栈维护一下.

栈内是可能"延续"到当前位置的之前的影子.那么显然比当前位置高的不可能.如果有和当前位置等高的影子,就延续过来,就可以少一个建筑,否则,就向栈里加入当前位置高度的影子.

 #include <bits/stdc++.h>
using namespace std; const int maxn=+;
int n,m,top,ans;
int a[maxn],s[maxn];
int main(){
scanf("%d%d",&n,&m); ans=n;
for(int i=;i<=n;i++) scanf("%d",&a[i]), scanf("%d",&a[i]);
for(int i=;i<=n;i++){
while(s[top]>a[i]) top--;
if(s[top]==a[i]) ans--;
else s[++top]=a[i];
}
printf("%d\n",ans);
return ;
}

1628: [Usaco2007 Demo]City skyline

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 432  Solved: 344
[Submit][Status][Discuss]

Description

BZOJ_1628_[Usaco2007_Demo]_City_skyline_(单调栈)

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

Silver

上一篇:android 资源文字ids的作用


下一篇:[译]JVM运行时数据区