首页 > 代码库 > HDU 1394 树状数组（逆序数）
HDU 1394 树状数组（逆序数）
Minimum Inversion Number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10100 Accepted Submission(s): 6192
For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
You are asked to write a program to find the minimum inversion number out of the above sequences.
题目意思：
给一个长度n的序列a1,a2....an-1,an。该序列逆序数为num0.
然后把序列首位元素a1弄到最后面得：
a2,a3....an-1,an,a1 此时逆序数为num1。
在把序列首位元素a2弄到最后面的：
a3,a4...an,a1,a2 此时逆序数num2.
。。。
不断的进行上面操作，每次得一个逆序数，求这些逆序数中最小的为多少。
逆序数可以由线段树、树状数组、归并排序求出，在这就不详细讲了，不懂的朋友可以百度。
非要按照上面操作模拟然后在找出最小的吗？no，这样的话一定会超时，下面说一个简单的分析思路：
设咱们第一次求出的逆序数为num0，第二次求出的逆序数为num1...依次类推，只需找出n-1次的逆序数就行了，以后就重复了，第一次逆序数用上面三种方法可求得（最好不要用归并排序，本题中咱们需要保存原序列，归并排序会打乱原序列，这样的话还要开一个辅助数组），num0就求出来了，观察上述操作，a1放到最后面的话，因为a1之前为首位，后面比a1大的即之前没和a1构成逆序数的数此时和a1构成了逆序数（设这些比a1大的数的数目为s1，比a1小的数的数目为s2），那么num0+1，而后面比a1小的即之前和a1构成逆序数的数此时不能和a1构成逆序数了，num0-s2，所以num1=num0+s1-s2。
然后a2位于首位，重复上述操作得num2。
。。。
这样下来num0----num(n-1)都求出来了，找其中最小的即为答案。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 #define N 5005 7 #define inf 999999999 8 9 int c[N];10 int a[N];11 12 int lowbit(int x){13 return x&(-x);14 }15 16 void update(int x){17 while(x<N){18 c[x]++;19 x+=lowbit(x);20 }21 }22 23 int get_sum(int x){24 int ans=0;25 while(x>0){26 ans+=c[x];27 x-=lowbit(x);28 }29 return ans;30 }31 32 main()33 {34 int n, i, j, k;35 while(scanf("%d",&n)==1){36 memset(c,0,sizeof(c));37 int num=0;38 for(i=1;i<=n;i++){39 scanf("%d",&a[i]);40 a[i]++;41 num+=get_sum(N-1)-get_sum(a[i]); 42 update(a[i]); 43 } //以上用树状数组求序列a的逆序数 44 int minh=inf;45 for(i=1;i<=n;i++)46 {47 num=num-(a[i]-1)+(n-a[i]); //每次由之前的逆序数推出此时的逆序数 48 minh=min(minh,num); //更新最小值 49 }50 printf("%d\n",minh);51 }52 }