本文共 762 字，大约阅读时间需要 2 分钟。

题目大意： 
就是问这个序列冒泡排序的话 需要交换多少次

解题思路： 
明确题意之后就非常好理解了 
对于每个数字来说交换了多少次 也就是在这个数出现之前有几个比他大的数字。累加即可。

这里维护一个树状数组，每次把a[i]的值更新为1，这样的话查询的时候1~a[i]的和就是这个数出现之前比他大的数字的个数。

#include 
   
    using namespace std;const int N = 1000+5;#define lowbit(x) (x&-x)int cnt,sum[N],a[N];void update(int index,int val){    for(int i=index;i<=cnt;i+=lowbit(i))        sum[i]+=val;    return ;}int getSum(int index){    int ans = 0;    for(int i=index;i>0;i-=lowbit(i))        ans+=sum[i];    return ans;}int main(){    while(~scanf("%d",&cnt)){        memset(sum,0,sizeof(sum));        for(int i=1;i<=cnt;i++)            scanf("%d",&a[i]);        int ans=0;        for(int i=cnt;i;i--){            ans+=getSum(a[i]);            update(a[i],1);        }        printf("%d\n",ans);    }    return 0;}
   

转载地址：http://ssali.baihongyu.com/