题目链接:https://vjudge.net/contest/182746#problem/C
转载于 >>>
题意描述:
给你一个有0--n-1数字组成的序列,然后进行这样的操作,每次将最前面一个元素放到最后面去会得到一个序列,那么这样就形成了n个序列,那么每个序列都有一个逆序数,找出其中最小的一个输出!
解题分析:
先利用线段树求出初始序列的逆序数,这里有一个非常巧妙的地方,由于比a[i]大的数是离散且连续的,所以可以用线段树来实现(与线段树节点的区间特性符合)。
#include<iostream> using namespace std; #define N 5005 struct { int l, r; int num; }tree[4 * N]; void creat(int i, int l, int r) //初始化该线段树 { int mid = (l + r) / 2; tree[i].l = l; tree[i].r = r; tree[i].num = 0; if (l == r) { return; } creat(i * 2, l, mid); creat(i * 2 + 1, mid + 1, r); } void updata(int i, int k) { if (tree[i].l == k && tree[i].r == k) { tree[i].num = 1; return; } int mid = (tree[i].l + tree[i].r) / 2; if (k <= mid) updata(i * 2, k); else updata(i * 2 + 1, k); tree[i].num = tree[i * 2].num + tree[i * 2 + 1].num; //trees[i].num表示符合[trees[i].l,trees[i].r]区间的数的个数 } int getsum(int i, int k, int n) //这个函数不太明白怎么实现的 { if (k <= tree[i].l&&tree[i].r <= n) { return tree[i].num; } else { int mid = (tree[i].l + tree[i].r) / 2; int sum1 = 0, sum2 = 0; if (k <= mid) sum1 = getsum(i * 2, k, n); if (n>mid) sum2 = getsum(i * 2 + 1, k, n); return sum1 + sum2; } } int main() { int n; while (scanf("%d", &n)>0) { int a[N]; creat(1, 0, n - 1); int i; int ans = 0; for (i = 0; i<n; i++) { scanf("%d", &a[i]); ans += getsum(1, a[i] + 1, n - 1); //a[i]+1~n-1代表比a[i]大的数,getsum()函数的作用是计算该序列前面有几个数比他大(因为此时只输入了它前面的数) updata(1, a[i]); } int minx = ans; for (i = 0; i<n; i++) //总共要将n个数全部移动一次到序列的最末端 { ans = ans + n - 2 * a[i] - 1; //当a[i]由第一个变为最后一个时,要加上a[i]后面大于a[i]的数的个数,有n-1-a[i]个,要 if (ans<minx) //减去a[i]后面小于a[i]的数的个数,有a[i]个(注意i是从0开始的) minx = ans; } printf("%d\n", minx); } return 0; }
2018-07-22
原文:https://www.cnblogs.com/00isok/p/9351602.html