hdu 1394 zoj 1484 求旋转序列的逆序数(并归排序)

发布时间:2016-12-9 15:59:41 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 1394 zoj 1484 求旋转序列的逆序数(并归排序)",主要涉及到hdu 1394 zoj 1484 求旋转序列的逆序数(并归排序)方面的内容,对于hdu 1394 zoj 1484 求旋转序列的逆序数(并归排序)感兴趣的同学可以参考一下。

题意:给出一序列,你可以循环移动它(就是把后面的一段移动到前面),问可以移动的并产生的最小逆序数。 求逆序可以用并归排序,复杂度为O(nlogn),但是如果每移动一次就求一次的话肯定会超时,网上题解都说可以用并归做,想了好久,最后发现"the next line contains a permutation of the n integers from 0 to n-1",坑爹的家伙,这些数竟然是从0到n-1的。 这样就可以做了,推导一下可以发现每移动一位,数列的逆序数就会又规律的变化,和它有关的且它是较大数的逆序数对会减小,其实就是序列排序完比它小的数的个数,其实就是它本身的值;而它是较小数的逆序数对就是比它大的个数。 所以只要排序一遍,求出当前逆序数,然后模拟一下循环一遍会产生的逆序数,取得最小值就行了。 代码: /* * Author: illuz <[email protected]> * Blog: http://blog.csdn.net/hcbbt * File: hdu1394.cpp * Lauguage: C/C++ * Create Date: 2013-08-30 10:28:05 * Descripton: hdu1394, Minimum Inversion Number, partitation, simutation */ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) #define repu(i, a, b) for (int i = (a); i < (b); i++) const int MAXN = 5100; int n, a[MAXN], b[MAXN], t[MAXN]; int cnt, Min, sum; void mergeSort(int* A, int x, int y) { if (y - x <= 1) return; int m = x + (y - x) / 2; mergeSort(A, x, m); mergeSort(A, m, y); int p = x, q = m, i = x; while (p < m || q < y) if (q >= y || (p < m && A[p] <= A[q])) t[i++] = A[p++]; else t[i++] = A[q++], cnt += m - p; repu(i, x, y) A[i] = t[i]; } int main() { while (scanf("%d", &n) != EOF) { rep(i, n) scanf("%d", &a[i]); int Min = 0xffffff; memcpy(b, a, sizeof(a)); cnt = 0; mergeSort(a, 0, n); sum = Min = cnt; rep(i, n) { sum = sum - b[i] + (n - 1 - b[i]); Min = min(Min, sum); } printf("%d\n", Min); } return 0; }

上一篇:JavaScript编程:JavaScript表单编程
下一篇:消息队列

相关文章

相关评论