HDU--1394

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394

分析：树状数组的应用。

Minimum Inversion Number

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define maxn 5005
 7 using namespace std;
 8 int c[maxn],num[maxn],n;
 9 int low_bit(int i)
10 {
11     return i&(-i);
12 }
13 void update(int i,int v)
14 {
15     while(i<=n){
16         c[i]+=v;
17         i+=low_bit(i);
18     }
19 }
20 int get_sum(int i)
21 {
22     int sum=0;
23     while(i){
24         sum+=c[i];
25         i-=low_bit(i);
26     }
27     return sum;
28 }
29 int main()
30 {
31     while(~scanf("%d",&n))
32     {
33         memset(c,0,sizeof(c));
34         int res=0;
35         for(int i=1;i<=n;i++)
36         {
37             scanf("%d",&num[i]);
38             res+=get_sum(n)-get_sum(num[i]+1);
39             update(num[i]+1,1);
40         }
41         int ans=res;
42         for(int i=1;i<=n;i++)
43         {
44             res+=n-num[i]*2-1;
45             ans=min(ans,res);
46         }
47         printf("%d
",ans);
48     }
49     return 0;
50 }

View Code