hdu1394 Minimum Inversion Number 线段树和树状数组

　　题意：

　　输入一个长度 n

　　第二行给出长度为n的数组，数组的值刚好为0到n-1这n个数。

然后每次把数组的第一个数放到最后一个，放n-1次，共有n个排列，这n个排列就有n个逆序数，输出这n个逆序数的最小值。

我的做法：

1、每次输入a[i]后，都把a[i] ++;

2、求出第一个排列的逆序数

3、递推求出所有的逆序数

那怎么求1呢？

对于每一个a[i],求出1到i-1 中比它大的个数，然后相加，即可得。若用朴素的查找，肯定会超时的，所以这里就利用线段树或者树状数组来快速查找。

线段树版本：

 1 #include<cstdio>
 2 #include<cstring>
 3 #define lson l,m,rt<<1
 4 #define rson m+1,r,rt<<1|1
 5 const int maxn=5010;
 6 int c[maxn<<2];
 7 int a[maxn];
 8 int sum[maxn];
 9 void pushup(int rt)
10 {
11     c[rt]=c[rt<<1]+c[rt<<1|1];
12 }
13 void update(int p,int add,int l,int r,int rt)
14 {
15     if(l==r){
16         c[rt]+=add;
17         return;
18     }
19     int m=(l+r)>>1;
20     if(p<=m)
21         update(p,add,lson);
22     else
23         update(p,add,rson);
24     pushup(rt);
25 }
26 int query(int L,int R,int l,int r,int rt)
27 {
28     if(L<=l&&R>=r)
29         return c[rt];
30     int m=(l+r)>>1;
31     int ret=0;
32     if(L<=m)
33         ret+=query(L,R,lson);
34     if(R>m)
35         ret+=query(L,R,rson);
36     return ret;
37 }
38 int main()
39 {
40     int n;
41     while(scanf("%d",&n)!=EOF){
42         sum[1]=0;
43         memset(c,0,sizeof(c));
44         for(int i=1;i<=n;i++){
45             scanf("%d",&a[i]);
46             a[i]++;
47             sum[1]+=query(a[i],n,1,n,1);
48             update(a[i],1,1,n,1);
49         }
50         for(int i=2;i<=n;i++)
51             sum[i]=sum[i-1]+n+1-2*a[i-1];
52         int ans=n*n;
53         for(int i=1;i<=n;i++)
54             if(sum[i]<ans)
55                 ans=sum[i];
56         printf("%d
",ans);
57     }
58     return 0;
59 }

View Code

用了46ms

树状数组版本：

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=5010;
 4 int c[maxn];
 5 int a[maxn];
 6 int sum[maxn];
 7 int lowbit(int x)
 8 {
 9     return x&(-x);
10 }
11 void update(int x,int d,int n)
12 {
13     while(x<=n){
14         c[x]+=d;
15         x+=lowbit(x);
16     }
17 }
18 int query(int x)
19 {
20     int ret=0;
21     while(x>0){
22         ret+=c[x];
23         x-=lowbit(x);
24     }
25     return ret;
26 }
27 int main()
28 {
29     int n;
30     while(scanf("%d",&n)!=EOF){
31         memset(c,0,sizeof(c));
32         sum[1]=0;
33         for(int i=1;i<=n;i++){
34             scanf("%d",&a[i]);
35             a[i]++;
36             sum[1]+=(i-1-query(a[i]));
37             update(a[i],1,n);
38         }
39         for(int i=2;i<=n;i++)
40             sum[i]=sum[i-1]+n+1-2*a[i-1];
41         int ans=n*n;
42         for(int i=1;i<=n;i++)
43             if(ans>sum[i])
44                 ans=sum[i];
45         printf("%d
",ans);
46     }
47     return 0;
48 }

View Code

也是46ms