題目：

資源限制
時間限制：1.0s 內存限制：256.0MB

問題描述

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。

分析：

這道題拿到手，第一反應排個序唄，暴力做，再一看數據范圍。哦，會超時，這時候就想起之前的那道樹狀數組判最小逆序對的題，樹狀數組能解決前面有多少個數比他小的問題。
故通過兩次樹狀數組，求得 某個小朋友 $i$ 會被交換的次數 $su[i]$
第一次 樹狀數組 順序找到 在小朋友 $i$左邊且比小朋友i身高低的人數$X$，那么在小朋友i左邊且比小朋友i身高高的人數為 $i?X$，提醒一下，此時還要減去當等于a[i]的所有數。所以找的是小于a[i]+1的所有數。
第二次 樹狀數組 逆序直接找到 在小朋友i右邊且比小朋友i身低的人數

AC模板：

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef long long ll; const int M=1e6+10; int n,ma; int a[M]; ll su[M],sm[M],num; int lowbit(int x){return x&(-x); } void build(int x){//建立關系，將大于x的數存入while(x<=ma+1){//注意此處是ma+1su[x]++;x+=lowbit(x);} } ll query(int x){//從先到后比x矮的小朋友個數ll ans=0;while(x>0){ans+=su[x];x-=lowbit(x);}return ans; } int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);ma=max(ma,a[i]);}for(int i=1;i<=n;i++){build(a[i]+1);sm[i]+=(i-query(a[i]+1));}memset(su,0,sizeof(su));for(int i=n;i>0;i--){build(a[i]+1);sm[i]+=query(a[i]);}for(int i=1;i<=n;i++)num+=(sm[i]+1)*sm[i]/2;printf("%lld\n",num);return 0; }

備戰ing ，題目分析簡略，見諒，轉載請注明出處。。。。。

總結

以上是生活随笔為你收集整理的蓝桥杯2014届试题9题 小朋友排队（树状数组+类逆序对）的全部內容，希望文章能夠幫你解決所遇到的問題。

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