JZOJ 1264. 亂頭髮節

1264. 亂頭髮節(badhair.pas/c/cpp) 
(File IO): input:badhair.in output:badhair.out

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。

6
10
3
7
4
12
2

5

 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 }