题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=1394
Minimum Inversion Number
Description
The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.
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.
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.
Input
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.
Output
For each case, output the minimum inversion number on a single line.
Sample Input
10
1 3 6 9 0 8 5 7 4 2
Sample Output
16
归并排序求逆序数。。
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #define mid ((l+r)>>1) 7 using std::min; 8 const int Max_N = 5010; 9 const int INF = ~0u >> 1; 10 int cnt, arr[Max_N], ret[Max_N], temp[Max_N]; 11 void Merge(int *A, int l, int m, int r) { 12 int p = 0; 13 int x = l, y = m + 1; 14 while (x <= m && y <= r) { 15 if (A[x] > A[y]) cnt += m - x + 1, temp[p++] = A[y++]; 16 else temp[p++] = A[x++]; 17 } 18 while (x <= m) temp[p++] = A[x++]; 19 while (y <= r) temp[p++] = A[y++]; 20 for (x = 0; x < p; x++) A[l + x] = temp[x]; 21 } 22 void MergeSort(int *A, int l, int r) { 23 if (l < r) { 24 MergeSort(A, l, mid); 25 MergeSort(A, mid + 1, r); 26 Merge(A, l, mid, r); 27 } 28 } 29 int main() { 30 #ifdef LOCAL 31 freopen("in.txt", "r", stdin); 32 freopen("out.txt", "w+", stdout); 33 #endif 34 int n; 35 while (~scanf("%d", &n)) { 36 for (int i = 0; i < n; i++) scanf("%d", &arr[i]), ret[i] = arr[i]; 37 cnt = 0; 38 MergeSort(arr, 0, n - 1); 39 int res = INF; 40 for (int i = 0; i < n; i++) { 41 cnt = cnt + n - ret[i] - ret[i] - 1; 42 res = min(res, cnt); 43 } 44 printf("%d ", res); 45 } 46 return 0; 47 }