Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：
n头牛排成一列，第n只牛在最前面，第1只牛在最后面。第i只牛能看到的牛的个数是，它前面的且没有被其他牛遮挡的牛的个数，遮挡的条件是高度大于或者相同。现在问所有牛能看到的牛的个数的和。
思路：单调栈。具体见代码。1A.
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月03日 星期三 05时12分47秒
4File Name :code/poj/3250.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <stack>
14#include <set>
15#include <map>
16#include <string>
17#include <cmath>
18#include <cstdlib>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=8E4+7;
35int a[N];
36int c[N];
37stack<int>stk;
38int n;
39int main()
40{
41 #ifndef ONLINE_JUDGE
42 freopen("code/in.txt","r",stdin);
43 #endif
44
45 scanf("%d",&n);
46 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
47
48 a[n+1] = inf;
49 stk.push(n+1);
50 int x;
51 for ( int i = n ; i >=1 ; i--)
52 {
53 for ( x = stk.top() ; a[x]<a[i] ; x = stk.top()) stk.pop();//找到第一个大于等于a[i]的位置
54 c[i] = x-1; //第一个大于等于a[i]的位置的左边就是i号牛能看到的最远的牛，c[i]-i就是i号牛能看到的牛的个数。
55 stk.push(i);
56 }
57// for ( int i = n; i >= 1 ; i--) cout<<"i:"<<i<<" c[i]:"<<c[i]<<endl;
58 LL ans = 0 ;
59 for ( int i = 1 ; i <= n ; i++) ans = ans + 1LL*(c[i]-i);
60 printf("%lld\n",ans);
61
62
63 #ifndef ONLINE_JUDGE
64 fclose(stdin);
65 #endif
66 return 0;
67}