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;

}

巴特西

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

最新文章

热门文章