hdu 1394

地址：http://acm.hdu.edu.cn/showproblem.php?pid=1394

题意：给n个数字（0到n-1无重复），可以拿前面任意m个放到末尾。求拿多少个数字放到末尾后数列的逆序数最小。

mark：非常经典的一个题目，来自zoj月赛。先用线段树/点树/树状数组/合并排序求出原数列的逆序数，然后递推出所有情况的逆序数取最小。

这题真的是非常经典，所以4种方法我都写了一次。

代码：

线段树（62ms、284k、991B）：

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

View Code

树状数组（46ms、224k、528B）：

 1 # include <stdio.h>
 2 # include <string.h>
 3 
 4 
 5 int a[5010], b[5010], n;
 6 void u(int v){while (v) b[v]++, v -= v & -v;}
 7 
 8 
 9 int q(int v){
10     int x = 0;
11     while (v <= n) x += b[v], v += v & -v;
12     return x;
13 }
14 
15 
16 int main ()
17 {
18     int x, y, i;
19     while (~scanf ("%d", &n))
20     {
21         memset (b, 0, sizeof(b)) ;
22         for (x = 0, i = 1; i <= n; i++)
23             scanf ("%d", &a[i]), x += q(a[i]+1), u(a[i]+1);
24         for (y = x, i = 1 ; i < n; i++)
25             y = y + (n - 1 - a[i]) - a[i],
26             (x > y) && (x = y);
27         printf ("%d
", x);
28     }
29     return 0;
30 }

View Code

点树（46ms、244k、712B）：

 1 # include <stdio.h>
 2 # include <string.h>
 3 
 4 
 5 int pt[10010], N ;
 6 int a[5010], n ;
 7 
 8 
 9 int Sum (int x)
10 {
11     int sum = 0;
12     for ( ; x > 1; x /= 2)
13         if (x&1) sum += pt[x/2] ;
14     return sum ;
15 }
16 
17 
18 void Add(int x)
19 {    
20     for (++pt[x] ; x > 1 ; x /= 2)
21         if (x%2==0) pt[x/2]++ ;    
22 }
23 
24 
25 int main ()
26 {
27     int sum, ans, i ;
28     while (~scanf ("%d", &n))
29     {
30         sum = 0 ;
31         for (N = 1 ; N < n ; N <<= 1) ;
32         memset(pt, 0, sizeof(pt)) ;
33         for (i = 0 ; i < n ; i++)
34         {
35             scanf ("%d", &a[i]) ;
36             sum += i-Sum(a[i]+N) ;
37             Add (a[i]+N) ;
38         }
39         ans = sum ;
40         for (i = 0 ; i < n -1 ; i++)
41         {
42             sum = sum + n-1 - 2*a[i] ;
43             if (sum < ans) ans = sum ;
44         }
45         printf ("%d
", ans) ;
46     }
47     return 0 ;
48 }

View Code

合并排序（31ms、224k、964B）：

 1 # include <stdio.h>
 2 
 3 
 4 int a[5010], b[5010], n ;
 5 int buff[5010] ;
 6 
 7 
 8 int merge_sort(int l,int r)
 9 {
10     int i, m = (l+r)>>1 ;
11     int p = l, q = m+1, rtn = 0 ;
12     if (l == r) return 0 ;
13     rtn += merge_sort(l, m) ;
14     rtn += merge_sort(m+1,r) ;
15     for (i = l ; i <= r ; i++)
16     {
17         if (p > m) buff[i] = a[q++] ;
18         else if (q > r) buff[i] = a[p++], rtn += q-m-1 ;
19         else if (a[p] < a[q])
20             buff[i] = a[p++], rtn += q-m-1 ;
21         else
22             buff[i] = a[q++] ;
23     }
24     for (i = l ; i <= r ; i++)
25         a[i] = buff[i] ;
26     return rtn ;
27 }
28 
29 
30 int inv () //求逆序数 
31 {
32     return merge_sort(0,n-1) ;
33 }
34 
35 
36 int main ()
37 {
38     int i, sum, ans ;
39     while (~scanf ("%d", &n))
40     {
41         sum = 0 ;
42         for(i = 0 ; i < n ; i++)
43             scanf ("%d", &a[i]) ;
44         for (i = 0 ; i < n ; i++)
45             b[i] = a[i] ;
46         sum = ans = inv() ;
47         for(i = 0 ; i < n-1 ; i++)
48         {
49             sum = sum + n - 1 - 2 * b[i] ;
50             if (sum < ans) ans = sum ;
51         }
52         printf ("%d
", ans) ;
53     }
54     return 0 ;
55 }

View Code

可以看出，线段树运行时间长，内存开销大，代码量大。相比之下，树状数组和点数的内存开销都少一些，时间也会快一些。代码量上树状数组最优。跑的最快的是合并排序，并且内存开销也很小，但代码量和线段树差不多。