[单调栈]poj 3250：Bad Hair Day

大致题意：
    一排共n头牛排队站在一起，给出队伍中每头牛的高度。每头牛只能看到站在他右边且个头比他小的牛。求出所有牛可以看到的牛数之和。

 

大致思路：

    做到poj3415，居然碰到“单调栈”这种牛逼的玩意，于是专门来把这道题切掉。所谓单调栈也就是每次加入一个新元素时，把栈中小于等于这个值的元素弹出。接下来回到这道题。求所有牛功能看到多少牛，可以转化为：这n头牛共能被多少头牛看见。当我们新加入一个高度值时，如果栈中存在元素小于新加入的高度值，那这个牛肯定看不见这个高度的牛，就把这个元素弹出。每次加入新元素，并执行完弹出操作后，栈中元素个数便是可以看见这个牛的“牛数”~~~。

 

 

#include<cstdio>
#include<cstring>
#include<stack>
#include<iostream>
using namespace std;
stack<long long>sta;
int main(){
    long long num,n,i,ans;
    while(scanf("%lld",&n)!=EOF){
        ans=0;
        scanf("%lld",&num);
        sta.push(num);
        for(i=1;i<n;i++){
            scanf("%lld",&num);
            while(!sta.empty()&&sta.top()<=num){
                sta.pop();
            }
            ans+=sta.size();
            sta.push(num);
        }
        printf("%lld\n",ans);
        while(!sta.empty())sta.pop();
    }
    return 0;
}

评论

2 楼 暴风雪 2012-09-10  

proverbs 写道

搜题意又搜到大神的了！O(∩_∩)O哈哈~
STO~

我是蒟蒻哇，这道题也是学别人的，不过单调找，单调队列的思想很重要的

1 楼 proverbs 2012-09-09  

搜题意又搜到大神的了！O(∩_∩)O哈哈~
STO~