問題描述

Alice是一個讓人非常愉躍的人!他總是去學習一些他不懂的問題，然后再想出許多稀奇古怪的題目。這幾天，Alice又沉浸在逆序對的快樂當中，他已近學會了如何求逆序對對數，動態維護逆序對對數等等題目，他認為把這些題讓你做簡直是太沒追求了，于是，經過一天的思考和完善，Alice終于拿出了一道他認為差不多的題目：

有一顆2n-1個節點的二叉樹，它有恰好n個葉子節點，每個節點上寫了一個整數。如果將這棵樹的所有葉子節點上的數從左到右寫下來，便得到一個序列a[1]…a[n]。現在想讓這個序列中的逆序對數量最少，但唯一的操作就是選樹上一個非葉子節點，將它的左右兩顆子樹交換。他可以做任意多次這個操作。求在最優方案下，該序列的逆序對數最少有多少。

Alice自己已近想出了題目的正解，他打算拿來和你分享，他要求你在最短的時間內完成。

輸入格式

第一行一個整數n。

下面每行，一個數x。

如果x=0，表示這個節點非葉子節點，遞歸地向下讀入其左孩子和右孩子的信息，如果x≠0，表示這個節點是葉子節點，權值為x。

輸出格式

輸出一個整數，表示最少有多少逆序對。

樣例輸入

3
0
0
3
1
2

樣例輸出

1

數據規模與約定

對于20%的數據，n <= 5000。

對于100%的數據，1 <= n <= 200000，0 <= a[i]<2^31。

以下是我對這題的理解。

題意：這題的大致意思是根據題目給定的數據建立一顆二叉樹，然后對這顆二叉樹進行調整，求調整前后最小的逆序對數。

思路：

1.首先輸入數據，buildTree函數利用輸入的數據建立一顆二叉樹。根據左右子樹的規模大小，merge函數把小規模子樹插入到大子樹規模上去，順便統計逆序對數。方便敘述，小規模子樹用T1，大規模子樹用T2表示。

2.rank函數是求T1的每一個節點在T2上的排名（即小于鍵值的節點個數），lens保存的是T1子樹大于T2的節點數量，rans保存的是T1子樹小于T2節點數量，lens和rans兩個變量相當于調整前后的逆序對數，兩者更小的值便是調整前后的最小逆序對數，用變量ans保存最小的逆序對數，從葉子節點一直到根節點計算調整前后的逆序對數,最后就是調整前后總的最小逆序對數。

3.這題使用的是SBT樹做的，當插入一個一個節點之后要對插入的節點，如果存在SBT不滿足條件的幾種情況，對插入后的樹進行調整，形成的樹是由所有的有效節點形成的。

4.此題核心函數是插入節點之后對樹的調整函數adjust函數以及求節點在樹種的排名rank函數這兩個函數；

使用c++編譯器進行編譯會有一部分超時，使用c編譯可以，注意c里面沒有bool類型，c++才有

SBT樹的講解：https://blog.csdn.net/zzkksunboy/article/details/73927513

代碼：

#include<stdio.h> #define N 200010//定義總的節點個數 long long ans = 0;//保存調整前后最小的逆序對數 int n,val,index=1;//n有效節點數，index為有效節點下標，val臨時輸入的值 //S保存的是以i為根節點的有效節點數目，left為i的左子樹，right為i的右子樹,key表示i的鍵值 int S[N],left[N],right[N],key[N]; int rRotate(int t){//對t節點進行右旋轉 int tem = left[t];left[t] = right[tem];right[tem] = t;S[t] = S[left[t]]+S[right[t]]+1;//修改其根節點的有效節點個數 S[tem] = S[left[tem]]+S[right[tem]]+1;return tem;//返回調整后的根節點 } int lRotate(int t){int tem = right[t];right[t] = left[tem];left[tem] = t;S[t] = S[right[t]]+S[left[t]]+1;S[tem] = S[right[tem]]+S[left[tem]]+1;return tem; } int adjust(int t,int flag){//根據flag來進行何種調整(flag不能使用bool類型，c沒有bool類型)if(flag){if(S[left[left[t]]]>S[right[t]] || S[right[left[t]]]>S[right[t]]){if(S[right[left[t]]]>S[right[t]]){left[t] = lRotate(left[t]);}return rRotate(t);}}else{if(S[right[right[t]]]>S[left[t]] || S[left[right[t]]]>S[left[t]]){if(S[left[right[t]]]>S[left[t]]){right[t] = rRotate(right[t]);}return lRotate(t);}}return t;//如果都不滿足，直接返回其原先節點 } int insert(int t,int node){ S[t]++;//t節點數增加1if(key[node]<key[t]){//根據node的值決定插入到t的左子樹還是右子樹 if(left[t]==0){//如果左子樹為空，直接接到左子樹上 left[t]=node;}else{//否則遞歸插入到左子樹上 left[t] = insert(left[t],node);}}else{if(right[t]==0){right[t]=node;}else{right[t] = insert(right[t],node);}}return adjust(t,key[node]<key[t]);//插入節點后要對平衡二叉樹進行調整 } int rank(int t,int val){//求val在以t為根節點的排名，就是求出小于val的節點個數 if(t==0)return 0;//如果節點為空，則返回0 if(val>=key[t]){return rank(right[t],val);}else{return rank(left[t],val)+1+S[right[t]];} } int merge(int node,int begin,int end){//把從begin-end的節點插入到大規模子樹中，并且統計其總的逆序對數long long lens=0,rans=0; int i;for(i=begin;i<end;i++){//計算逆序對數int tem = rank(node,key[i]); lens += tem;rans += S[node] - tem;}ans += lens < rans ? lens : rans;//ans保存較小的逆序對數 for(i=begin;i<end;i++){//將begin-end的節點插入到以node為根節點的子樹上 left[i]=right[i]=0;S[i]=1;node = insert(node,i);}return node; } int buildTree(){scanf("%d",&val);if(val!=0){left[index]=right[index]=0;S[index]=1;key[index]=val;return index++;}int a = index;int lt = buildTree();//遞歸創建左子樹int b = index;int rt = buildTree();//遞歸創建右子樹int c = index;if(b - a > c - b){//b-a表示左子樹的規模，c-b表示右子樹的規模，將規模小的子樹插入到規模更大的子樹 return merge(lt,b,c);}else{return merge(rt,a,b);} } int main(){scanf("%d",&n);//總結點的個數buildTree();printf("%I64d\n",ans); return 0; }

?

總結

以上是生活随笔為你收集整理的蓝桥杯 ALGO-7 逆序对的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。