题解：AT_donuts_2015_3 行列のできるドーナツ屋

· · 题解

题目传送门

题目简述

有 n 个人排队，第 1 个人排在最前面，他们的身高分别为 H_{1} \sim H_{n}。求对于每个 i \in [1,n]，第 i 个人向前看能看到几个人，并且看到的人里面最前面的人的身高是看到的人里面最高的。

主要思路

采用单调栈的算法，本题与洛谷主题库 P2866 [USACO06NOV] Bad Hair Day S 几乎相同，只不过操作顺序反了过来，答案变成了依次输出。

单调栈的主要思想即在栈内保持一个单调的序列，在本题中每次输出的答案即栈内的元素数，因为在这一个序列中，不管当前人的身高多高，栈内的人他都能看见。最后不断弹掉栈顶直到空栈或栈顶的人的身高大于等于当前人的身高，保持序列的单调性。

由于 stack 与 queue 一样效率都不高，所以建议手写，并且本题中操作也只有 push() 与 pop() 两种操作。

时间复杂度

O(n)

AC Code

#include<cstdio>
#include<iostream>
using namespace std;

#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#endif

#define endl '\n'
#define pc putchar
#define gc getchar
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repr(i, a, b) for (int i = a; i >= b; i--)
void print(int x) { if (x < 0) { pc('-'); x = -x; }if (x > 9) { print(x / 10); }pc(char(x % 10 + 48)); }
inline int read_int() { int f = 1, x = 0; char ch = gc(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = gc(); }while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }return x * f; }
// ----------------------------

// ----------------------------
int st[N];
// ----------------------------

int main() {
    int n = read_int(); 
    // ----------------------------
    int h, top = 0;
    rep(i, 1, n) {
        h = read_int();
        print(int(top));
        pc('\n');
        while (top > 0 && st[top] < h) --top;
        st[++top] = h;
    }
    return 0;
}
/*
                 .-~~~~~~~~~-._       _.-~~~~~~~~~-.
             __.'              ~.   .~              `.__
           .'//   A    C    之   \./  之    真    理  \`.
         .'//                     |                     \`.
       .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \`.
     .'//.-"                 `-.  |  .-'                 "-.\`.
   .'//______.============-..   \ | /   ..-============.______\`.
 .'______________________________\|/______________________________`.
*/

后言

建议降黄，正文中提到的 P2866 也是黄。