Description

Some of Farmer John'sNcows (1 ≤N≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows' heads.

Each cowihas a specified heighth_i(1 ≤h_i≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cowican see the tops of the heads of cows in front of her (namely cowsi+1,i+2, and so on), for as long as these cows are strictly shorter than cowi.

Consider this example:

??????? =
=?????? =
=?? -?? =???????? Cows facing right -->
=?? =?? =
= - = = =
= = = = = =
1 2 3 4 5 6

Cow#1 can see the hairstyle of cows #2, 3, 4
Cow#2 can see no cow's hairstyle
Cow#3 can see the hairstyle of cow #4
Cow#4 can see no cow's hairstyle
Cow#5 can see the hairstyle of cow 6
Cow#6 can see no cows at all!

Letc_idenote the number of cows whose hairstyle is visible from cowi; please compute the sum ofc₁throughc_N.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.

Input

Line 1: The number of cows,N.
Lines 2..N+1: Linei+1 contains a single integer that is the height of cowi.

Output

Line 1: A single integer that is the sum ofc₁throughc_N.

Sample Input

6
10
3
7
4
12
2

Sample Output

5

分析：

這個題的實質是求從隊列中任意一個數開始連續下降的數的個數的和。所以需要知道從隊列中的某個數開始有多少個連續的下降的數。所以考慮使用單調隊列。由于這道題不是求一個區間的最值，所以不用記錄隊首，隊列退化為棧。而且沒有區間長度限制，所以不用記錄下標，也不用保留原數據，降低了空間復雜度。時間復雜度為O(n)，注意sum的范圍。
code：

?

View Code #include<stdio.h>
int stack[80010];
int main()
{
int top=0,i,n,p;
__int64 sum=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&p);
while(top>0&&stack[top]<=p)
top--;
sum+=top;
stack[++top]=p;
}
printf("%I64d\n",sum);
return 0;
}

轉載于:https://www.cnblogs.com/dream-wind/archive/2012/03/14/2396291.html

總結

以上是生活随笔為你收集整理的POJ 3250 Bad Hair Day【单调队列】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。