[Python] P2866 [USACO06NOV] Bad Hair Day S

发表于 分类于

农夫约翰有 N 头奶牛正在过乱头发节。

每一头牛都站在同一排面朝右，它们被从左到右依次编号为 1, 2, ⋯, N。编号为 i 的牛身高为 hi。第 N 头牛在最前面，而第 1 头牛在最后面。

对于第 i 头牛前面的第 j 头牛，如果 hi > hi + 1, hi > hi + 2, ⋯, hi > hj，那么认为第 i 头牛可以看到第 i + 1 到第 j 头牛。

定义 Ci 为第 i 头牛所能看到的牛的数量。请帮助农夫约翰求出 C1 + C2 + ⋯ + CN。

输入格式

输入共 N + 1 行。

第一行为一个整数 N，代表牛的个数。
接下来 N 行，每行一个整数 ai，分别代表第 1, 2, ⋯, N 头牛的身高。

输出格式

输出共一行一个整数，代表 C1 + C2 + ⋯ + CN。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
6
10
3
7
4
12
2

输出 #1

1
5

说明/提示

数据规模与约定

对于 100% 的数据，保证 1 ≤ N ≤ 8 × 104，1 ≤ hi ≤ 109。

题解

单调栈求最近较大位置

1
2
3
4
5
6
7
8
9
10
11
12
13
stack = []
ans = {}

n = int(input())
cows = [int(input()) for _ in range(n)]

for i, h in reversed(list(enumerate(cows))):
    while stack and cows[stack[-1]] < h: stack.pop()
    ans[i] = stack[-1] if stack else n
    stack.append(i)

#print(ans)
print(sum(ans[i]-i-1 for i in range(n)))