URL: http://poj.org/problem?id=3250
题目大意：农场里有n头奶牛(1<=n<=8e4)排成一列，每头牛能看到他后面严格比他矮的奶牛，直至遇到比他高或一样高的奶牛为止。求所有奶牛能看见的其他奶牛的总数。
思路分析：
很多类似的题，看上去都很像逆序数，然而和逆序数有着细微的差别。这导致了这种题采用了完全不同的算法。
如果直接考虑每头牛能看到多少其他奶牛，显然较难。我们可以“正难则反”地考虑每头牛能被看到几次。
于是可以找到一种思路：维护一个单调递减的栈s. 输入第i个数后，栈中的元素个数减去1就等于第i头牛能被看到的次数。减去1是因为要去掉自己，自己不能被自己看见。
最后将这些值相加即可。
部分易错点：
1. 要用long long或unsigned long long.
2. 注意是严格小于号。
代码呈现：
(Time: 688MS; Memory: 2588K; Code: 477B)
#include<cstdio> #include<stack> using namespace std; const int MAXN = 8e4; stack<long long> s; long long a[MAXN+2]; int n; long long ans; int main() { int i,j,t; scanf("%d",&n); ans = 0; for(i=1; i<=n; i++) { scanf("%lld",&a[i]); if(s.empty()) { s.push(a[i]); continue; } t = s.top(); if(a[i] >= t) { while(!s.empty() && a[i] >= s.top()) { s.pop(); } } s.push(a[i]); ans+=(s.size()-1); } printf("%lld\n",ans); return 0; }