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

1 2 3

4 3 2 1

Sample Output

（我的代码中此题与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个元素增加val
14 {
15     //i的祖先都要增加val
16     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]个元素+1
53             count+=i-b[i]-1;
54         }
55 
56         
57         cout<<count<<endl;
58 
59     }
60 
61     return 0;
62 }

View Code