POJ3250(Bad Hair Day)

单调队列练习题。

题目大意：n个牛排成一列向右看，牛i能看到牛j的头顶，当且仅当牛j在牛i的右边并且牛i与牛j之间的所有牛均比牛i矮。设牛i能看到的牛数为C_i，求∑C_i

View Code

 1 #include <stdio.h>
 2 #define N 8000001
 3 #define INF 0x7fffffff
 4 int a[N];
 5 int q[N],front,rear;
 6 int main()
 7 {
 8     int i,n;
 9     long long ans;
10     while(~scanf("%d",&n))
11     {
12         for(i=0;i<n;i++)    scanf("%d",&a[i]);
13         a[n]=INF;
14         front=rear=0;
15         ans=0;
16         for(i=0;i<=n;i++)
17         {
18             while(front<rear&&a[q[rear-1]]<=a[i])
19             {
20                 ans+=i-q[rear-1]-1;
21                 rear--;
22             }
23             q[rear++]=i;
24         }
25         printf("%lld\n",ans);
26     }
27     return 0;
28 }