POJ 3250 Bad Hair Day

POJ 3250 Bad Hair Day

題目概述:

給n隻牛的高度，然後n隻牛都站好一排向右看，每一隻牛可以看到在下一個比自己還要高(≧)的牛之前所有的牛的髮型。求所有牛能看到的牛數量的sum，

思路:

維護一個遞減的stack，做法就大概是下圖這樣了。

一開始要丟個INF是為了不讓stack裡是空的，造成呼叫top()時造成RE的困擾，還有一些方便的地方，會讓code簡單多了。

最後丟個INF-1是為了讓剩下在stack裡的東西也加上答案，但又不能算到(INF,0)才會讓INF-1。

AC code:

//By SCJ

//POJ 3250

#include<iostream>

#include<stack>

using namespace std;

#define endl '\n'

#define INF 2000000000

int main()

{

//ios::sync_with_stdio(0);

//cin.tie(0);

int n;cin>>n;

long long ans=0;

stack<pair<int,int>> s;

s.push(make_pair(INF,0));

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

{

int tp;cin>>tp;

while(tp>=s.top().first) ans+=(i-s.top().second-1),s.pop();

s.push(make_pair(tp,i));

}

while(s.size()>1)

{

ans+=(n-s.top().second);s.pop();

}

cout<<ans<<endl;

}

/*

6

5 2 4 2 6 1

*/