洛谷P2866《[USACO06NOV]糟糕的一天Bad Hair Day》

十月 06, 2018 3147

有点难想的单调栈模板题

题目地址

暂不提供题面，请自行到洛谷查看题面。

Input / Output 格式 & 样例

输入格式

第一行：一个数N表示奶牛的数量。

第2到N+1行：第i+1行包含一个整数表示第i头奶牛的高。

输出格式

第一行：一个整数，即c1到cN的和

输入样例

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

输出样例

1
5

解题思路

这就是一个单调栈的模板

循环读入，每次push读入的数进一个单调栈并维护这个栈的单调性，最后答案累加栈的大小-1即可（显然题意说明奶牛是看不见自己的发型的，要把自己减去）

以上操作的推导过程：

  • 我们对于当前读进去的奶牛的高度，计算栈中还有多少比它矮的，把它们pop出来（维护单调性）
  • 这个过程其实就是在计算当前的奶牛能被多少奶牛看见
  • 接下来累计答案
  • 最后将当前奶牛的高度push进去

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

/* -- Defined Words -- */

using namespace std;

namespace FastIO {
    void DEBUG(char comment[], int x) {
        cerr << comment << x << endl;
    }

    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }

    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

namespace Solution {
    const int MAXN = 80000 + 10;
    struct Stack {
        int seq[MAXN];
        int tail;
        
        Stack() {
            memset(seq, 0, sizeof(seq));
            tail = 0;
        }
        void Pop() {
            tail--;
        }
        int Top() {
            return seq[tail];
        }
        bool isEmpty() {
            return tail == 0;
        }
        void Push(int x) {
            while (!isEmpty() && Top() <= x) Pop();
            seq[++tail] = x;
        }
        int Size() {
            return tail;
        }
        int __tail_location() {
            return tail;
        }
    } stk;
	// 手写栈无所畏惧
	
    int n;
}

int main(int argc, char *const argv[]) {
    #ifdef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
    #endif
    using namespace Solution;
    using namespace FastIO;
    n = getint();
    long long int ans = 0;
    For (i, 1, n) {
        int x = getint();
        stk.Push(x);
        ans += stk.Size() - 1;
    }
    cout << ans << endl;
    return 0;
}