[算尽天下系列第2期]计蒜客·排序
[算尽天下系列第2期]计蒜客·排序
题目描述
你需要分析排序算法，将 个互不相同的整数，通过交换两个相邻的元素使得数列有序的最少交换次数。
比如，原数列为：
排序后的数列为： 。
样例
输入格式
第一行一个整数 。
接下来 行，每行一个整数 。
5
9
1
0
5
4输出格式
输出一个整数，表示操作次数。
6算法与数据结构
树状数组
离散化
题解
这是一道用树状数组做的题，还要用到离散化的技巧。
一次有效的交换意味着什么呢？
为了使序列有序，一次有效的交换应该是后一个较小的数与他前一个较大的数交换，那么单独一个数字的交换次数，应该是这个数字前面比它大的数字的个数。
换句话说，当一个数字出现的时候，出现在它左边且比它大的数字的个数，就是当出现到这个数字为止（这个数字右边的数字还没出现）时，这个数字要到正确位置上交换的次数。
对每一个位置上的数字累加这样的次数，就是答案。
更一般的，令初始 sum = 0，对于第 i 个数字，出现在它左边且比它大的数字的个数如果是 x，就令 sum += x，遍历所有的数字，最后得到的累加和，就是答案。
现在剩一个问题：怎么知道出现在左边的、比自己大的数字有多少？对于遍历到的第 i 个数字（记为 x），如果在遇到它的时候，单点更新树状数组 change(x)，改变的动作是加 1，即计数，即令 x 出现的次数加 1，那么，对于 getSum(x) 操作，就是求出从 1 到 x 的数字一共出现了多少次，即，不小于 x 的数字有多少个。
当我们得知了这个结果以后，由于出现在 x 右边的数字是还没有遇到的，所以，不小于 x 的数字都出现在 x 的左边，那就可以简单地使用 i + 1 - getSum(x) 得到出现在 x 左边、比自己大的数字的个数。
这个公式是显然成立的：对于第 i 个数字，目前已经出现的所有数字一共是 i + 1 个，在这些数字里，不小于 x 的有 getSum(x) 个，所以，大于 x 的有 i + 1 - getSum(x) 个。并且，这些数字要么是 x 本身，要么出现在 x 的左边。
累加所有的 i + 1 - getSum(x)，得到答案。
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &x);
change(x); // 更新树状数组，记下新的数 x
ans += i + 1 - getSum(x);
// getSum(x) 是已出现的（在 x 左边的）小于等于 x 的数
// x 在第 i + 1 位，它和它的左边有 i + 1 个数
// 所以它左边比它大的数有 i + 1 - getSum(x) 个，有那么多个逆序对，就需要交换那么多次
}
printf("%d", ans);但是，由于数字范围实在是太大了，我们需要用到离散化的技巧，即将大范围的数字映射到小范围，因为我们只关心数字之间值的大小关系，而不关心具体的数值。
for (int i = 0; i < n; i++) {
scanf("%d", &x[i]);
dis[i] = x[i]; // 读入数据，复制一份以便离散化处理
}对于 C++，可以使用 unique() 函数来去重，首先对 dis数组排序，然后去重，得到去重后的长度 length。在去重后的数组中，用二分查找 x[i] 所在的位置，并用这个位置作为 x[i] 离散化后的值。
sort(dis, dis + n); // 对数据排序
int length = unique(dis, dis + n) - dis; // 利用 unique 去重，使大小与下标对应，并得到去重后的长度
for (int i = 0; i < n; i++) {
int index = lower_bound(dis, dis + length, x[i]) - dis; // 在去重后的数组中，使用二分查找找到 x[i] 所在位置
x[i] = index + 1; // 用这个位置作为离散后的值，由于树状数组下标从 1 开始，因此加 1
}之后的操作与之前类似，遍历 x 数组，change(x[i])，并计算 ans += i + 1 - getSum(x[i])。
最后要注意一下，ans 是 long long 范围的。
以及提一句，unique 和 lower_bound 返回值都是 long long int，直接降级到 int 是一种不好的做法。
完整代码
#include <bits/stdc++.h>
using namespace std;
int n = 0;
const int MAX_N = 500007;
int C[MAX_N] = {0}; // 树状数组
int x[MAX_N] = {0}; // 记录原始数据
int dis[MAX_N] = {0}; // 离散化数据
long long ans = 0;
int lowBit(int x) {
return x & -x; // return x & (x ^ (x - 1))
}
int getSum(int x) {
int res = 0;
while (x != 0) {
res += C[x];
x -= lowBit(x);
}
return res;
}
void change(int x) {
while (x <= MAX_N) {
C[x]++;
x += lowBit(x);
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &x[i]);
dis[i] = x[i]; // 读入数据，复制一份以便离散化处理
}
sort(dis, dis + n); // 对数据排序
int length = unique(dis, dis + n) - dis; // 利用 unique 去重，使大小与下标对应，并得到去重后的长度
for (int i = 0; i < n; i++) {
int index = lower_bound(dis, dis + length, x[i]) - dis; // 在去重后的数组中，使用二分查找找到 x[i] 所在位置
x[i] = index + 1; // 用这个位置作为离散后的值，由于树状数组下标从 1 开始，因此加 1
}
for (int i = 0; i < n; i++) {
change(x[i]); // 更新树状数组，记下新的数 x
ans += i + 1 - getSum(x[i]);
// getSum(x) 是已出现的（在 x 左边的）小于等于 x 的数
// x 在第 i + 1 位，它和它的左边有 i + 1 个数
// 所以它左边比它大的数有 i + 1 - getSum(x) 个，有那么多个逆序对，就需要交换那么多次
}
printf("%lld", ans);
return 0;
}腾讯云开发者
