問題描述

　　n 個小朋友站成一排。現在要把他們按身高從低到高的順序排列，但是每次只能交換位置相鄰的兩個小朋友。

　　每個小朋友都有一個不高興的程度。開始的時候，所有小朋友的不高興程度都是0。

　　如果某個小朋友第一次被要求交換，則他的不高興程度增加1，如果第二次要求他交換，則他的不高興程度增加2（即不高興程度為3），依次類推。當要求某個小朋友第k次交換時，他的不高興程度增加k。

　　請問，要讓所有小朋友按從低到高排隊，他們的不高興程度之和最小是多少。

　　如果有兩個小朋友身高一樣，則他們誰站在誰前面是沒有關系的。

輸入格式

　　輸入的第一行包含一個整數n，表示小朋友的個數。
　　第二行包含 n 個整數 H1 H2 … Hn，分別表示每個小朋友的身高。

輸出格式

　　輸出一行，包含一個整數，表示小朋友的不高興程度和的最小值。

樣例輸入

3
3 2 1

樣例輸出

9

樣例說明

　　首先交換身高為3和2的小朋友，再交換身高為3和1的小朋友，再交換身高為2和1的小朋友，每個小朋友的不高興程度都是3，總和為9。

數據規模和約定

　　對于10%的數據， 1<=n<=10；
　　對于30%的數據， 1<=n<=1000；
　　對于50%的數據， 1<=n<=10000；
　　對于100%的數據，1<=n<=100000，0<=Hi<=1000000。

直接做法超時！！

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll s[100000]; //交換次數 ll height[100000];//身高數組 ll n,sum=0; int main() {ios::sync_with_stdio(false);cin>>n;for(int i=0;i<n;i++){cin>>height[i];}for(int i=0;i<n;i++)for(int j=i;j<n;j++){if(height[i]>height[j]){s[i]++;s[j]++;}}//尋找逆序對//標記好交換次數for(int i=0;i<n;i++){sum=sum+(s[i]+1)*s[i]/2;//累加}cout<<sum<<endl;return 0; }

說白了就是針對每一個元素，看看它之前有幾個大于它的元素，之后有幾個小于它的元素，然后記錄這個元素在逆序對中出現的次數，也就是含這個元素的逆序對的個數，然后再將每個元素的不高興程度相加即可。

樹狀數組實際上是由兩部分組成：數據數組+統計數組，只看數據數組（這個描述。。。）

由于樹狀數組是從1開始的，而題目中小盆友的身高可以為0（真是長見識了），所以我們將每個小盆友的身高加1然后作為樹狀數組的下標，將數值1存到相應的位置.

第一次讀入3，此時讀入的數據量為1個，變成這樣

C[1] ???????C[2] ???????C[3] ???????C[4] ??????C[5] ???????C[6] ????????C[7] ????????C[8]
??0 ????????????0 ???????????0 ???????????1 ???????????0 ????????????0 ????????????0 ?????????????0
可以看到sum(C[1],C[4])=1(可以由樹狀數組的統計數組得到)，這個是小于等于3的數字的個數，也就是說當輸入第一個數字3的時候沒有比它小的數字存在，這時我們用 輸入數字總數-sum(C[1],C[4])=0，也就是說大于3的數字的個數為0，我們令b[0]=0.

第二次讀入2，此時讀入的數據量為2個，變成這樣

C[1] ???????C[2] ???????C[3] ???????C[4] ??????C[5] ???????C[6] ????????C[7] ????????C[8]
??0 ????????????0 ???????????1 ???????????1 ????????????0 ???????????????0 ????????????0 ?????????????0

可以看到sum(C[1],C[3])=1，任然不存在比它小的數，但此時輸入的數據總量為2，而2-1=1，就是說，存在一個數在2之前并且大于2，這個數當然就是3，我們另b[1]=1.

第三次讀入1，此時讀入的數據量為3，變成這樣

C[1] ???????C[2] ???????C[3] ???????C[4] ??????C[5] ???????C[6] ????????C[7] ????????C[8]
??0 ????????????1 ????????????1 ????????????1? ? ? ? ? ??? 0 ?????????? 0 ??????????0 ???????????0
可以看到sum(C[1],C[2])=1，任然不存在比它小的數，但此時輸入的數據總量為3，而3-1=2，就是說，存在兩個數在1之前并且大于1，這個數當然就是2，3，我們另b[2]=2.

到此，我們已經算出了每個數前面的較大的數的個數了，數據存在num[]中，現在我們再反過來遍歷，1，2，3，但這次我們不再用總數減去sum了，而直接求sum，求出來的自然就是，每個數后面的較小的數的個數，然后將得到的數值累加到相應的b[i]中，最終我們會得到b[0]=2,b[1]=2,b[2]=2,分別對應num[0]=3,num[1]=2,num[2]=1。

求得了每個小盆友被移動的次數，我們需要計算其不高興程度，這里實際上可以事先打個表，就是將被移動n次后的不高興值全算出來，然后直接用就可以了，這里，我們將其存到total[]數組中，而且total[2]=3，所以總不高興值就是9.

需要注意的是如果重復的數字出現怎么辦，如果出現，實際上出問題的會是求每個數之前較大數的那部分，因為用到了數的總個數，如果出現一樣的數，就會導致相減后的結果偏大，而且正好是大了 重復量-1 ，那么我們就可以算出重復量，然后將這一部分減去就行，關鍵是怎么算重復量，實際也很簡單，通過樹狀數組，我們可以求得sum(1,a)和sum(1,a+1)，其中輸入的數字為a，前者算出的小于a的數的個數，后者算出的是小于等于a的數的個數，兩個一減就是等于a的個數。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1111111; const int N=111111; ll c1[maxn],c2[maxn],b[maxn]; ll num[N]; ll total[N]; void init() {memset(c1,0,sizeof(c1));memset(c2,0,sizeof(c2));total[0]=0;for(int i=1;i<=N;i++)total[i]=total[i-1]+i; } int lowbit(int x) {return x&-x; } ll query(ll c[],int x) {ll ans=0;while(x){ans+=c[x];x-=lowbit(x);}return ans; } void add(ll c[],int x,ll v) {while(x<maxn){c[x]+=v;x+=lowbit(x);} } int main() {ios::sync_with_stdio(false);init();int n;cin>>n;for(int i=0;i<n;i++){cin>>num[i];add(c1,num[i]+1,1);b[i]=i-query(c1,num[i]);b[i]=b[i]-(query(c1,num[i]+1)-query(c1,num[i])-1);}for(int i=n-1;i>=0;i--){add(c2,num[i]+1,1);b[i]=b[i]+query(c2,num[i]);}ll ans=0;for(int i=0;i<n;i++){ans+=total[b[i]];}cout<<ans<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的小朋友排队（树状数组）的全部內容，希望文章能夠幫你解決所遇到的問題。

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