单调栈3_水到极致的题 HDOJ4252

A Famous City

题目大意给出正视图每一列为楼的高度最少有几座楼

坑点楼高度可以为0 代表没有楼

贡献了两发RE 原因 if(!s.empty()&&tem){s.push(tem); continue;}并不能筛去空栈且 tem为0的情况

改为 if(!s.empty()){if(tem) s.push(tem); continue;} 后AC

题目思路维护一个单调递增的栈假如新加入的楼高度小于top元素那我们知道top元素一定是单独的一栋楼我们就pop掉 ans++

如果等于top 那么可以认为这两个是一栋楼（最少）

如果大于pop 就添加下一个

操作结束后剩余在栈内的元素每一个必然是独立的一栋楼

楼的高度0 一定要特判

对栈进行top pop 这些操作前一定要判empty啊

代码如下

#include<cstdio>

#include<map>

//#include<bits/stdc++.h>

#include<vector>

#include<stack>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<cstdlib>

#include<climits>

#define PI acos(-1.0)

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

typedef __int64 int64;

const ll mood=1e9+;

const int64 Mod=;

const double eps=1e-;

const int N=2e7+;

const int MAXN=1e5+;

inline void rl(ll&num){

    num=;ll f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<='')num=num*+ch-'',ch=getchar();

    num*=f;

}

inline void ri(int &num){

    num=;int f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<='')num=num*+ch-'',ch=getchar();

    num*=f;

}

int getnum()//相邻的个位整数输入 如想分别保存1234 输入连续的1234 a[i]=getnum();就可以实现

{

    char ch=getchar();

    while((ch<'' || ch>'') && ch!='-')

        ch=getchar();

    return (ch-'');

}

inline void out(int x){ if(x<) {putchar('-');  x*=-;}if(x>) out(x/);    putchar(x%+''); }

int main()

{

   int n,ci=;

   while(scanf("%d",&n)!=EOF)

   {

       int tem;

       ll ans=;

       stack<int>s;

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

       {

           ri(tem);

           if(s.empty())

           {

               if(tem)s.push(tem);

               continue;

           }

           if(s.top()==tem) continue;

           if(tem<s.top())

           {

               while(!s.empty()&&s.top()>tem)

               {

                   s.pop();

                   ans++;

               }

               if(!s.empty()&&s.top()==tem) continue;

               else{

                  if(tem)s.push(tem);

               }

           }

           else{

                if(tem)s.push(tem);

           }

       }

       printf("Case %d: ",++ci);

       ans+=s.size();

       cout<<ans<<endl;

   }

   return ;

}

AC代码

巴特西

单调栈3_水到极致的题 HDOJ4252

最新文章

热门文章