有 N(1 ≤n ≤ 80,000) 头很关注自己发型的牛 站在一排 ，望着同一个方向。 每头牛都 有一个高度 hi (1 ≤ hi ≤ 1,000,000,000) 。每头牛只能看见自己前方比自己矮的的发型。请计算出所有牛能看到的发型总数
第一行个整数： N
接下来 N行：每一个整数，表示第 i头牛的高度 hi
一个整数，表示所有的牛能看到发型总。
6
10
3
7
4
12
2
5
1 ≤ N ≤ 80,000
维护一个单调递减的栈，栈的大小就是每个奶牛最多被看到多少次。
#include<iostream> #include<cstdio> #define N 80010 using namespace std; long long s[N]; long long n,x,top,ans; int main() { cin>>n; for (int i=1;i<=n;i++) { cin>>x; while (top && x>=s[top]) top--; ans += top; s[++top] = x; } cout<<ans; }
原文：http://www.cnblogs.com/liumengyue/p/5517882.html