CF1437D Minimal Height Tree

发布于 2020-10-28  32 次阅读


CF1437D

Description

Monocarp有一棵树,可是他已经忘记了它的形态。但是他有这棵树的bfs序,并且对于每一个节点,bfs都会按照升序遍历它的子节点。现在给出这个bfs序,求出这棵树的最小深度。

Solution

先观察一下这个BFS序的性质

因为它给的BFS是按照升序访问子节点的,那么对于每个点后面出现的节点,如果它后面的点比他的编号还小,说明要新开一层,否则就可以一直堆在一层

举个例子:1 4 3 2

1已经确定是根,那么1的第一个子节点就是4,观察到4是目前1的子节点中编号最小的,如果我们要把2也弄成1的子节点,那么按照BFS序,2应该在4前面出现,所以这样是不合法的,说明2要新开一层成为4的子节点

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 2e5 + 5;

int T, n, ans;
int a[SIZE], dep[SIZE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void bfs()
{
    std::queue < int > q;
    memset(dep, 0, sizeof(dep));
    q.push(1);
    int pos = 2;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans = std::max(ans, dep[u]);
        int lst = pos;
        if (pos > n) break;
        while (a[pos + 1] > a[pos] && pos < n) ++ pos;
        for (int i = lst; i <= pos; ++ i) {
            dep[a[i]] = dep[u] + 1;
            q.push(a[i]);
        }
        ++ pos;
    }
}

int main()
{
    T = read();
    while (T --) {
        n = read();
        for (int i = 1; i <= n; ++ i) a[i] = read();
        ans = 0;
        bfs();
        for (int i = 1; i <= n; ++ i) ans = std::max(ans, dep[i]);
        printf("%d\n", ans);
    }
    return 0;
}

朴实沉毅