bzoj1628 [Usaco2007 Demo]City skyline（单调栈）

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

题目的$w$没有意义

我们发现高度$h$出现一次时，答案+1

$h$在一个先增后降的序列中出现两次时，显然答案也只要+1

那么我们可以设$ans=n$

考虑维护一个单调递增栈，当某个数出现2次时，$ans-1$即可

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define re register

 using namespace std;

 int n,q,h,w,st[],tp,ans;

 int main(){

     scanf("%d%d",&n,&w); ans=n;

     for(re int i=;i<=n;++i){

         scanf("%d%d",&q,&h);

         while(tp&&st[tp]>h) --tp;

         if(st[tp]==h) --ans;

         else st[++tp]=h;

     }printf("%d",ans);

     return ;

 }

巴特西