算法|题解

计蒜客 – 排序

凝神长老 · 2月14日 · 2020年 · · · 732次已读

计蒜客 排序

题目描述

你需要分析排序算法,将 $n$ 个互不相同的整数,通过交换两个相邻的元素使得数列有序的 最少交换次数。
比如,原数列为: $9,1,0,5,4$ 排序后的数列为: $0,1,4,5,9$。

样例

输入格式
第一行一个整数 $n(n\leq500000)$。
接下来 $n$ 行,每行一个整数 $a_i(a_i\leq10^9)$。

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])

最后要注意一下,anslong long 范围的。

以及提一句,uniquelower_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;
}
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论