题意:给出照片中从左到右的建筑物高度,判断最少可能有几栋楼.(矮的楼可以被高的挡住)
思路:
单调队列.
因为只要出现矮的楼,那么在它之前的比它高的楼都可以被确定是独立的楼,将它们出队,并计数.
相同高度的视为同一楼.
出现更高的楼的话就加入队列.
最后队伍里剩下的楼一并计数.
需要注意当队伍为空时,或者输入楼高为0时需要特殊处理,否则将越界.
#include <cstdio> #include <cstring> using namespace std; const int MAXN = 100005; int main() { int q[MAXN],rear,cnt,n,cas = 0; while(scanf("%d",&n)==1) { int t,sub = 0; cnt = 0; rear = 0; while(sub<n && scanf("%d",&t) && !t ) sub++; if(sub==n) { printf("Case %d: 0\n",++cas); continue; } q[rear] = t; for(int i=sub+1;i<n;i++) { scanf("%d",&t); if(rear==-1) { if(t) q[++rear] = t; continue; } while(t<q[rear]) { rear--; cnt++; if(rear==-1) break; } if(rear==-1) { if(t) q[++rear] = t; continue; } if(t>q[rear]) q[++rear] = t; } printf("Case %d: %d\n",++cas,cnt+rear+1); } }