hdu 1394 937ms 水过

这题，开始TLE，然后我就改变方法了，只用一次归并排序求逆序数，然后再推出其他的。
937水过，显然不是好办法。。。
 1 #include <stdio.h>
 2 #define maxn 5050
 3 int a[maxn];
 4 int b[maxn];
 5 int c[maxn];
 6 int num[maxn];
 7 int cnt;
 8 void change(int n,int m)
 9 {
10     int i,j;
11     for(i=0;i<n;++i)
12         a[i]=num[i];
13     for(i=0;i<m;++i)
14     {
15         b[i]=a[i];
16     }
17     for(i=0;i<n-m;++i)
18     {
19         a[i]=a[i+m];
20     }
21     for(i=n-m,j=0;i<n;++i,++j)
22     {
23         a[i]=b[j];
24     }
25     return;
26 }
27 void MergeSort(int l, int r){
28     int mid, i, j, tmp;
29     if( r > l+1 ){
30         mid = (l+r)/2;
31         MergeSort(l, mid);
32         MergeSort(mid, r);
33         tmp = l;
34         for( i=l, j=mid; i < mid && j < r; ){
35             if( a[i] > a[j] ){
36                 c[tmp++] = a[j++];
37                 cnt += mid-i; 
38             }
39             else c[tmp++] = a[i++];
40         }
41         if( j < r ) for( ; j < r; ++j ) c[tmp++] = a[j];
42         else
43             for( ; i < mid; ++i )
44                 c[tmp++] = a[i];
45         for ( i=l; i < r; ++i ) a[i] = c[i];
46     }
47 }
48 
49 int main()
50 {
51     int n,m,i,res;
52     while(~scanf("%d",&n))
53     {
54         for(i=0;i<n;++i)
55             scanf("%d",&num[i]);
56         res=100000000;
57         cnt=0;
58         change(n,0);
59         for(m=0;m<n;++m)
60         {
61             if(m==0)
62                 MergeSort(0,n);
63             else
64             {
65                 for(i=1;i<n;++i)
66                 {
67                     if(a[0]<a[i])
68                         cnt++;
69                     else
70                         cnt--;
71                 }
72             }
73             res=res<cnt?res:cnt;
74             change(n,m);
75         }
76         printf("%d\n",res);
77     }
78     return 0;
79 }