Codeforces Round 826 pD

題目連結

https://codeforces.com/problemset/problem/1741/D

題目概要

給你一個 1\; 2 …m 但沒有排序的數列，其中 m=2^n, n \in N。
這些數字要被放在一個完全二元樹的樹葉(葉節點)中。
定義此完全二元樹是 “beautiful” 的若且唯若葉節點的數值剛好由左而右遞增。
我們可以做的操作是對任一節點，將他的左右子樹互換。
請問最少幾次操作可以讓樹變成 “beautiful” 的，如果做不到輸出-1。

提示1

判斷做不做得到與怎麼做可以分開。

提示2

怎麼做可以快速分辨是否成功。想想線段樹。

想法

仿造線段樹的作法，我們可以直接建立一顆完全二元樹，也可以用線段樹取代。我使用指標實作完全二元樹，在每個節點中增加一個數mn表示這棵子樹的所有節點的最小值。如果左子樹的最小值大於右子樹的最小值，則樹就需要旋轉(交換左右子樹)。

而分辨能否成功則可以用左右子樹最小值的差，如果可以成功旋轉，則所有節點的左右子樹最小值差一定要是 2^{該節點的高度-1}。而顯然滿足這條件就可以成功藉由有限次操作使樹變得 “beautiful“。

程式碼

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

int INF=0x3f3f3f3f;

struct binary_tree{
    struct node{
        node *lch,*rch;
        int mn=INF,val=0;

        node(){
            lch=rch=nullptr;
        }

        void swap_subtree(){
            swap(lch,rch);
        }
    };

    node *rt=new node();
    int idx=0,h=0;

    int test(node *n,int hi){
        if(!n->lch){
            return 0;
        }

        if(abs(n->lch->mn - n->rch->mn)!=1<<(hi-2)){
            return -1;
        }

        int ret=0;
        if(n->lch->mn > n->rch->mn){
            ret++;
            n->swap_subtree();
        }

        int ls=test(n->lch,hi-1),rs=test(n->rch,hi-1);
        if(ls==-1 || rs==-1){
            return -1;
        }

        ret+=ls+rs;
        return ret;
    }

    int test(){
        return test(rt,h);
    }

    void build(int h,node *n,vector<int> &v){
        if(h<=1){
            n->mn=n->val=v[idx];
            idx++;
            return;
        }
        n->lch=new node();
        n->rch=new node();
        build(h-1,n->lch,v);
        build(h-1,n->rch,v);
        if(n->lch && n->rch){
            n->mn=min(n->lch->mn,n->rch->mn);
        }
    }

    binary_tree(vector<int> v){
        int n=v.size();
        while(n>0){
            h++; n>>=1;
        }
        build(h,rt,v);
    }

    void delete_tree(node *n){
        if(!n) return;
        if(n->lch) delete_tree(n->lch);
        if(n->rch) delete_tree(n->rch);
        delete(n);
    }

    ~binary_tree(){
        delete_tree(rt);
    }
};

void solve(){
    int m;
    cin>>m;
    vector<int> v(m);
    for(auto &i:v) cin>>i;

    binary_tree cbt(v);
    cout<<cbt.test()<<"\n";
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}