问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1007http://acm.pku.edu.cn/JudgeOnline/problem?id=2299思路:
求逆序对的个数
这两题的基本问题是一致的，给定一个数组(包括字符串)，求出逆序对的个数
1. 最简单的方法
两层循环，复杂度O(n^2)
1 int
2 inversion_cal(char *str)
3 {
4 int i, j, count = 0;
5 int len = strlen(str);
6 for(i=0; i<len; i++)
7 for(j=i+1; j<len; j++)
8 if(str[i] > str[j])
9 ++count;
10 return count;
11 }
2.
归并排序＆分治思想其实，只要将归并排序稍加修改，就是一个求解逆序对个数问题的O(nlgn)方法
要理解的是这其中涉及的分治思想(三步骤):
a. 分解为子问题
b. 求解子问题
c. 合并子问题的解来得到原问题的解
具体对应到求逆序对个数的问题:
a. 将原数组分解为前后两个子数组
b. 求解子数组的逆序对个数
c. 合并前后子数组，同时计算逆序对个数(这个是指逆序对的第一个数在前子数组中，而第二个数在后子数组中)
1 long long
2 merge_count(long *arr, long *temp, long begin, long end)
3 {
4 if(begin >= end)
5 return 0;
6 long i, j, k, mid = (begin+end)/2;
7 long long rt = 0;
8 rt += merge_count(arr, temp, begin, mid);
9 rt += merge_count(arr, temp, mid+1, end);
10 i = k = begin;
11 j = mid+1;
12 while(i<=mid && j<=end) {
13 if(arr[i] <= arr[j])
14 temp[k++] = arr[i++];
15 else {
16 temp[k++] = arr[j++];
17 rt += (mid-i+1);
18 }
19 }
20 for( ; i<=mid; i++)
21 temp[k++] = arr[i];
22 for( ; j<=end; j++) {
23 temp[k++] = arr[j];
24 rt += (mid-i+1);
25 }
26 /* copy */
27 for(k=begin; k<=end; k++)
28 arr[k] = temp[k];
29 return rt;
30 }
3. 特例方法
针对PKU 1007该题的特殊性: 字符串中只包含A, G, T, C四个字母，还有一种更加简单的O(n)方法
1 int
2 inversion_cal2(char *str)
3 {
4 int i, temp[4], count = 0;
5 int len = strlen(str);
6 memset(temp, 0, sizeof(temp));
7 for(i=len-1; i>=0; i--) {
8 switch(str[i]) {
9 case 'A':
10 ++temp[0];
11 break;
12 case 'C':
13 ++temp[1];
14 count += temp[0];
15 break;
16 case 'G':
17 ++temp[2];
18 count += (temp[0]+temp[1]);
19 break;
20 case 'T':
21 ++temp[3];
22 count += (temp[0]+temp[1]+temp[2]);
23 break;
24 }
25 }
26 return count;
27 }