JZOJ 1264. 乱头发节

traveller-ly 2018-07-19 原文

JZOJ 1264. 乱头发节

Description

　　农民John的某 N 头奶牛 (1 <= N <= 80,000) 正在过乱头发节！由于每头牛都意识到自己凌乱不堪的发型，FJ 希望统计出能够看到其他牛的头发的牛的数量。　　每一头牛 i有一个高度 h[i] (1 <= h[i] <= 1,000,000,000)而且面向东方排成一排(在我们的图中是向右)。因此，第i头牛可以看到她前面的那些牛的头，（即i+1, i+2,等等），只要那些牛的高度严格小于她的高度。
每一头牛 i有一个高度 h[i] (1 <= h[i] <= 1,000,000,000)而且面向东方排成一排(在我们的图中是向右)。因此，第i头牛可以看到她前面的那些牛的头，（即i+1, i+2,等等），只要那些牛的高度严格小于她的高度。
例如这个例子:
=
= =
= =
= – = 牛面向右侧 –>
= = =
= – = = =
= = = = = =
1 2 3 4 5 6

牛#1 可以看到她们的发型 #2, 3, 4
牛#2 不能看到任何牛的发型
牛#3 可以看到她的发型 #4
牛#4 不能看到任何牛的发型
牛#5 可以看到她的发型 6
牛#6 不能看到任何牛的发型!
让 c[i] 表示第i头牛可以看到发型的牛的数量；请输出 c[1] 至 c[N]的和。如上面的这个例子，正确解是3 + 0 + 1 + 0 + 1 + 0 = 5。

Input

Line 1: 牛的数量 N。
Lines 2..N+1: 第 i+1 是一个整数，表示第i头牛的高度。

Output

　　Line 1: 一个整数表示c[1] 至 c[N]的和。

Sample Input

Sample Output

做法：维护一个高度不上升的队列，并更新队列中每个高度对应的牛能看到的头发的数量。

代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <string>
 4 #include <iostream>
 5 #define N 80007
 6 #define LL long long
 7 using namespace std;
 8 LL h[N], n, ans;
 9 struct arr
10 {
11     int x, hi;
12 }f[N];
13 
14 LL read()
15 {
16     LL s = 0;
17     char ch = getchar();
18     while (ch < '0' || ch > '9')    ch = getchar();
19     while (ch >= '0' && ch <= '9')    s = s * 10 + ch - '0', ch = getchar();
20     return s;
21 }
22 
23 int main()
24 {
25     freopen("badhair.in", "r", stdin);
26     freopen("badhair.out", "w", stdout);
27     n = read();
28     for (int i = 1; i <= n; i++)
29         h[i] = read();
30     int head = 1, tail = 0;
31     f[++tail].hi = h[n];
32     for (int i = n - 1; i >= 1; i--)
33     {
34         int l = 0, ac = 0;
35         for (int j = tail; j >= head; j--)
36             if (h[i] > f[j].hi)
37             {
38                 ac += f[j].x + 1;
39                 l++;
40             }
41             else break;
42         tail = tail - l + 1;
43         f[tail].hi = h[i];
44         f[tail].x = ac;
45         ans += ac;
46     }
47     cout << ans;
48     fclose(stdin);
49     fclose(stdout);
50 }