只有脚踩上去才知其远近和曲折

P1908_逆序对

P1908 逆序对

归并排序解法

解题思路

归并排序原理

原数组 arr,从数组左半部分取出一个元素a~i~,从数组右半部分取出一个元素a~j~,如果 a~i~ <= a~j~,则将 a~i~ 放到数组 temp 中,依次类推,再将数组 temp 拷贝回数组的相应位置。

解题方法

采用归并排序,可以利用分治的思想,将数组分为左右两部分,因为我们采用归并排序,所以左右两部分都是相对有序的,例如:

left right
5, 6, 7, 8 1, 2, 3, 4

数组中 1 比左数组中所有元素都小,所以把 1 放入 temp 数组,此时左数组中所有元素都可以和 1 组成逆序对,所以逆序对总数加上左数组中没有放入 temp 数组中元素的个数。

code

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long LL;
const int LEN = 500010;

int arr[LEN] = {0}, temp[LEN] = {0};
LL ans = 0;

// 快速读入
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar(); }
    return x * f;
}

// 归并排序
void merge_sort(int l, int r) {
    if (r - l < 2) return ;
    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid, r);
    int i = l, j = mid, k = 0;
    while (i < mid || j < r) {
        if (j >= r || (i < mid && arr[i] <= arr[j])) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            // 此时左侧没有放入 temp 数组中的元素都大于 arr[j]
            // 所以逆序对的总数加上这些元素的个数
            ans = ans + (mid - i);
        }
    }
    for (i = l; i < r; ++i) arr[i] = temp[i - l];
    return ;
}

int main() {
    int n = read();
    for (int i = 0; i < n; ++i) arr[i] = read();
    merge_sort(0, n);
    printf("%lld\n", ans);
    return 0;
}

树状数组

解题思路

学过树状数组后,本题的思路并不难想

  1. 先将数据进行离散化,采用由大到小排序(注意:数值相等时,序号大的放前面
  2. 使用【单点更新 区间查询】,每当我把第i个元素插入时,便计算一次1 ~ i-1的前缀和,即计算在它前面有多少比它大的

code

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define lowbit(a) ((a) & (-a))
#define MAXN 500010
int tree[MAXN];
int n;

struct Array {
    int num, ind;
    bool operator< (const struct Array tmp) const {
        if (num == tmp.num) return ind > tmp.ind;
        return num > tmp.num;
    }
};
struct Array arr[MAXN];

void add(int x, int k) {
    while (x <= n) tree[x] += k, x += lowbit(x);
    return ;
}

int get_sum(int x) {
    int ret = 0;
    while (x > 0) ret += tree[x], x -= lowbit(x);
    return ret;
}

int main() {
    long long sum = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &arr[i].num), arr[i].ind = i + 1;
    sort(arr, arr + n);
    for (int i = 0; i < n; i++) {
        add(arr[i].ind, 1);
        sum += get_sum(arr[i].ind - 1);
    }
    printf("%lld\n", sum);
    return 0;
} 
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注