首页 > 代码库 > HDU 2689 Sort it (树状数组)
HDU 2689 Sort it (树状数组)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2689
Sort it
Problem Description
You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need.
For example, 1 2 3 5 4, we only need one operation : swap 5 and 4.
Input
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.
Output
For each case, output the minimum times need to sort it in ascending order on a single line.
Sample Input
3
1 2 3
4
4 3 2 1
Sample Output
0
6
（我的代码中 此题与b[i]数组密切相关
b[i]表示
假如给你一个数组a[ ] = {2,5,3,4,1},求b[i]，b[i] 表示在a[1],a[2]...a[i-1]中(即位置i的左边)小于等于a[i]的数的个数。）
好像大神们都不是我这样做的， 我有走了奇葩路线 呵呵。。
1 #include<iostream> 2 3 using namespace std ; 4 5 int sum[1005]; 6 int n ; 7 8 int lowbit(int x) //取x的最低位1，比如4，则返回4，如5，则返回1 9 {10 return x&(-x);11 }12 13 void update(int i, int val) //将第i个元素增加val14 {15 //i的祖先都要增加val16 while(i <= n)17 {18 sum[i] += val;19 i += lowbit(i); //将i的二进制未位补为得到其祖先20 }21 }22 23 int Sum(int i) //求前i项的和24 {25 int s = 0;26 //将前i项分段27 while(i > 0)28 {29 s += sum[i];30 i -= lowbit(i); //去掉i的二进制最后一个31 }32 return s;33 }34 35 int main()36 {37 int i;38 int a[1005],b[1005];39 while(scanf("%d",&n)!=EOF)40 {41 int count=0;42 memset(b,0,sizeof(b));43 memset(sum,0,sizeof(sum));44 for(i=1;i<=n;i++)45 {46 scanf("%d",&a[i]);47 }48 49 for(i=1;i<=n; i++)50 {51 b[i] = Sum(a[i]); //求前a[i]项的和52 update(a[i],1); //第a[i]个元素+153 count+=i-b[i]-1;54 }55 56 57 cout<<count<<endl;58 59 }60 61 return 0;62 }