[单调栈]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;}