题意
求环形数组的最小逆序数。
思路
如何求逆序对请参考hdu 1394 求循环串的最小逆序数 暴力法 线段树 归并排序3种方法(hnust_xiehonghao)。
本题使用暴力方法也可以通过，但前提是需要知道一个结论：如果是0到n的排列，那么如果把第一个数放到最后，对于这个数列，逆序数是减少a[i],而增加n-1-a[i]的。
代码（线段树优化方法）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; const int MAXN = 5005; int segTree[MAXN*4]; #define LCH(n) (n << 1) #define RCH(n) ((n << 1) + 1) #define PAR(n) (n >> 1) int H;//the start position of the leafs void segTree_init(int n){ H = 1; while (H < n) { H <<= 1; } memset(segTree, 0, sizeof(segTree[0]) * 2 * H); } void segTree_point_deltaupdate(int pos, int delta){ pos = pos+H-1; segTree[pos] += delta; while (pos != 1) { pos = PAR(pos); segTree[pos] = segTree[LCH(pos)] + segTree[RCH(pos)]; } } int segTree_qres; void segTree_query(int l,int r, int cur = 1, int cl = 1, int cr = H){ //init:cur=1, cl = 1, cr = H if (cl > r || cr < l) { //this interval is outside the request return; }else if(cl >= l && cr <= r){ //this interval is inside the request segTree_qres += segTree[cur]; }else{ //this interval is partially crossed with the request segTree_query(l, r, LCH(cur), cl, cl+(cr-cl+1)/2-1); segTree_query(l, r, RCH(cur), cl+(cr-cl+1)/2, cr); } } int sig[MAXN]; int main(){ int n; while (scanf(" %d",&n) != EOF) { segTree_init(n); memset(sig, 0, sizeof(int)*n+2); int tmp = 0; for (int i = 1; i <= n; i++) { scanf(" %d",&sig[i]); segTree_qres = 0; segTree_query(sig[i]+2, n); tmp += segTree_qres; segTree_point_deltaupdate(sig[i]+1, 1); } int res = tmp; for (int i = 1; i <= n; i++) { tmp = tmp - (sig[i]*2) + n - 1; res = min(res,tmp); } printf("%d\n",res); } return 0; } |
