問題:
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 }