POJ 3250 Bad Hair Day 单调栈

题目意思：
n头奶牛排成一排，且面朝右方。每一头奶牛只能看到高度比自己矮的奶牛。问每个奶牛能看到奶牛数目的和是多少。

本题要点：
1、单调栈的入门题目
2、关键是， 答案要用 long long.
int 会溢出

#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
using namespace std;
const int MaxN = 80010;
int n;
int cows[MaxN];
int Right[MaxN];	// right[i]表示能够看到的右边的牛 的下标int main()
{
    while(scanf("%d", &n) != EOF){
    for(int i = 1; i <= n; ++i){
    scanf("%d", &cows[i]);}stack<int> s;for(int i = n; i >= 1; --i){
    while(!s.empty() && cows[i] > cows[s.top()])	{
    s.pop();}if(s.empty()){
    Right[i] = n;	// 右边的全部能看到}else{
    Right[i] = s.top() - 1;}s.push(i);}long long ans = 0;for(int i = 1; i <= n; ++i){
    ans += Right[i] - i;	}printf("%lld\n", ans);}return 0;
}/* 6 10 3 7 4 12 2 *//* 5 */