[单一栈]poj 3250:Bad Hair Day
[单调栈]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; }