codeforces-Ed97-D

codeforces-Ed97-D

十月 30, 2020

D. Minimal Height Tree

  • 题意

给出一个BFS程序

1
2
3
4
5
6
7
8
a = [] # the order in which vertices were processed
q = Queue()
q.put(1) # place the root at the end of the queue
while not q.empty():
    k = q.pop() # retrieve the first vertex from the queue
    a.append(k) # append k to the end of the sequence in which vertices were visited
    for y in g[k]: # g[k] is the list of all children of vertex k, sorted in ascending order
        q.put(y)

已知上图中序列a(BFS的访问顺序)

要求还原出一个以1号点为根的树 它的最小深度是多少

  • 题解

观察BFS程序发现对于一个点 访问它子节点的编号顺序是递增的

也就是说a序列中对于一个点i 它之后连续 的一段[i+L,i+R]是升序的

那么[i+L,i+R]都可以被归为点i的子节点 这样贪心构造的树能使深度最小

比如对于1 5 6 4 2 3

可以划分为{1}{5,6}{4}{2,3}

5,6作为1的子节点 4作为5的子节点 2,3作为6的子节点

深度最小为2，贪心构造的思路比较显然

具体实现比较巧妙用类似dp的方式

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<ll,ll>
const int Max=2e5+5;
const int Mod=1e9+7;
const int inf=0x3f3f3f3f;

/*

*/
int arr[Max];
int deep[Max];
int main(){
    Turnoff;
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        int cnt=1;deep[1]=0;
        for(int i=1;i<=n;i++)cin>>arr[i];
        for(int i=2;i<=n;i++){
            ///若不符合升序则相邻两个点必然不在同一个点下作为子节点
            ///所以cnt++
            if(arr[i]<arr[i-1])cnt++;
            deep[i]=deep[cnt]+1;
            ///cnt为i的父节点
        }
        cout<<deep[n]<<endl;
    }
}