Minimal Height Tree

提交

题意: 给定一棵树的遍历顺序，一个节点的子树遍历顺序是递增的，问这棵树的最小高度是多少

分析: 处理手法还算常见的贪心,记录上一层还没有孩子的节点和当前层有几个节点了，然后模拟就行（要想高度尽可能低，那么每一层最好都填满）

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long

int n;
void solve(){
    cin>>n;
    int ans = 0;
    int p = 0,q = 0;//上一层还有空闲的节点，当前层有的节点
    int root,last;
    cin>>root;last=root;
    for(int i = 2;i<=n;++i){
        int x;cin>>x;
        if(last>x){
            if(p==0) ans++,p = q-1,q = 1;
            else p--,q++;
        }else q++;
        last = x;
    }
    cout<<++ans<<"\n";
}

signed main(){
    ios;
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}