题意描述:
给你一个有 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;
- }
来源: http://www.bubuko.com/infodetail-2696305.html