Educational Codeforces Round 97 (Rated for Div. 2) D. Minimal Height Tree (贪心)

题意:有一个从根节点\(BFS\)得来的序列(每次\(bfs\)子节点的时候保证是升序放入队列的),现在让你还原树(没必要和之前相同),问能构造出的最小的树的深度.

题解:不看根节点,我们从第二个位置开始,如果某一段元素升序,那么就让他们变为上一层某个结点的儿子,否则,如果上一层还有另外的父节点的话,就作为它的子儿子,如果没有父亲结点可以连的话,就只能去下一层了,具体实现的话,我们可以统计每层结点的个数,如果下一层出现了降序的情况,就减去之前统计的个数,不断往复即可.

代码:

int t;
int n;
int a[N];
int cnt[N];
int ans;int main() {
    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    scanf("%d",&t);
    while(t--){
        ans=1;
        scanf("%d",&n);
        for(int i=0;i<n;++i) scanf("%d",&a[i]);
        int i=1;
        cnt[0]=1;
        while(i<n){
            int now=cnt[ans-1]; //上一层的结点数
            cnt[ans]=0;
            while(now>0){
                now--;
                if(i==n) continue;
                i++;
                cnt[ans]++;      //统计当前这一层的结点数
                while(i<n && a[i]>a[i-1]){   //升序,全部连给上一层的某个结点
                    cnt[ans]++;   //统计当前这一层的结点数
                    i++;
                }
            }
            ans++;
        }
        printf("%d\n",ans-1);
    }
    return 0;
}