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

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

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

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

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

樣例說明
首先交換身高為3和2的小朋友，再交換身高為3和1的小朋友，再交換身高為2和1的小朋友，每個小朋友的不高興程度都是3，總和為9。
數(shù)據(jù)規(guī)模和約定
對于100%的數(shù)據(jù)，1< =n< =100000，0< =Hi< =1000000。

輸入
輸入的第一行包含一個整數(shù)n，表示小朋友的個數(shù)。
第二行包含 n 個整數(shù) H1 H2 … Hn，分別表示每個小朋友的身高。
輸出
輸出一行，包含一個整數(shù)，表示小朋友的不高興程度和的最小值。
樣例輸入
3
3 2 1
樣例輸出
9
思路：我們要計(jì)算每一個數(shù)的移動次數(shù)。每一個數(shù)的移動次數(shù)等于大于它但是先出現(xiàn)的，和小于它但是后出現(xiàn)的個數(shù)。樹狀數(shù)組解決就可以了。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; int c[maxx]; int a[maxx],b[maxx],ans[maxx]; int n;inline int lowbit(int x){return x&-x;} inline void update(int cur,int v) {while(cur<=maxx){c[cur]+=v;cur+=lowbit(cur);} } inline int query(int cur) {int sum=0;while(cur){sum+=c[cur];cur-=lowbit(cur);}return sum; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];sort(b+1,b+1+n);memset(c,0,sizeof(c));for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;//事先離散化，減少空間復(fù)雜度。for(int i=1;i<=n;i++){ans[i]=(a[i]-1-query(a[i]-1))+(query(maxx)-query(a[i]));update(a[i],1);}//for(int i=1;i<=n;i++) cout<<ans[i]<<" ";cout<<endl;ll sum=0;for(int i=1;i<=n;i++) sum+=(ll)((ll)(1+ans[i])*(ll)(ans[i]))/2ll;//注意long long，白wa了一發(fā)cout<<sum<<endl;return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯][历届试题]小朋友排队（树状数组）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。