首页 > 代码库 > HDU 1394 Minimum Inversion Number 【逆序数】
HDU 1394 Minimum Inversion Number 【逆序数】
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1394
题目大意:给一个n,然后给出一组0~n-1的序列,求这个序列的逆序数,以及交换之后的逆序数中的最小值。交换规则是:
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)
比如我们已经得到了 4 3 2 1 0 的逆序数是10,则
4交换到末尾后 3 2 1 0 4 对于元素4来说,逆序数先是减少了4,然后增加了4 -4,最后的逆序数是 6
3交换到末尾后 2 1 0 4 3 对于元素3来说,逆序数先是减少了3,然后增加了4 -3,最后的逆序数是 4
然后循环可以得到逆序数的最小值。
//从归并排序到数列的逆序数对 #include <stdio.h> int g_nCount; void mergearray(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) //a[i] 前面的数 a[j] 后面的数 { if (a[i] < a[j]) temp[k++] = a[i++]; else { temp[k++] = a[j++]; //a[j]和前面每一个数都能组成逆序数对 g_nCount += m - i + 1; } } while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[first + i] = temp[i]; } void mergesort(int a[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; mergesort(a, first, mid, temp); //左边有序 mergesort(a, mid + 1, last, temp); //右边有序 mergearray(a, first, mid, last, temp); //再将二个有序数列合并 } } bool MergeSort(int a[], int n) { int *p = new int[n]; if (p == NULL) return false; mergesort(a, 0, n - 1, p); return true; } int main() { const int MAXN = 5005; int a[MAXN] ,b[MAXN]; int T; while(~scanf("%d",&T)) { for(int i=0;i<T;i++) scanf("%d",&a[i]),b[i]=a[i]; g_nCount = 0; MergeSort(a, T); //printf("逆序数对为: %d\n", g_nCount); int ans = g_nCount; int sum = g_nCount; for(int i = 0; i < T; i++ ) { //printf("%d\n",sum); sum = sum - (b[i]) + (T -1 - b[i]); if(ans > sum) ans = sum; } printf("%d\n",ans); } return 0; }
HDU 1394 Minimum Inversion Number 【逆序数】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。