问题 C: 求逆序对

2024-01-07 17:56:34
题目描述

给定一个序列a1,a2,…,an,如果存在i<j并且ai>aj,那么我们称之为逆序对,求逆序对的数目。

注意:n<=105,ai<=105

输入

第一行为n,表示序列长度。

接下来的n行,第i+1行表示序列中的第i个数。

输出

所有逆序对总数。

样例输入
4
3
2
3
2
样例输出
3

问题分析

直观方法:

最直接的方法是使用两层循环遍历所有元素对,检查是否构成逆序对。但这种方法的时间复杂度为O(n2),对于大数据量来说效率较低。

高效算法:

归并排序提供了一种更有效的方式来计算逆序对。

在归并排序的过程中,当一个元素从右半部分移动到左半部分时,它与左半部分所有剩余元素构成逆序对。

这样可以在O(nlogn) 的时间复杂度内计算出逆序对的总数。

分治策略:

使用分治方法将序列分成更小的子序列,分别计算每个子序列的逆序对,然后合并结果。

在合并两个已排序的子序列时,可以计算跨越两个子序列的逆序对。

#include <bits/stdc++.h>
#define int long long // 使用长整型
using namespace std;

// 定义一个函数 merge,用于合并两个子数组并计算逆序对
int merge(vector<int>& a, int l, int mid, int r) {
    vector<int> temp(r - l + 1); // 创建一个临时数组存储合并后的结果
    int i = l, j = mid + 1, k = 0, count = 0; // 初始化指针和计数器

    // 合并两个子数组
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            // 如果左侧元素小于等于右侧元素,复制左侧元素
            temp[k++] = a[i++];
        } else {
            // 如果左侧元素大于右侧元素,复制右侧元素
            // 并增加逆序对的数量(左侧剩余的元素个数)
            temp[k++] = a[j++];
            count = count + (mid - i + 1);
        }
    }
    // 复制剩余的左侧元素
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    // 复制剩余的右侧元素
    while (j <= r) {
        temp[k++] = a[j++];
    }
    // 将合并后的数组复制回原数组
    for (int i = l, k = 0; i <= r; i++, k++) {
        a[i] = temp[k];
    }
    return count; // 返回计数的逆序对数量
}

// 定义一个函数 mS(mergeSort 的缩写),用于递归地分治和合并
int mS(vector<int>& a, int l, int r) {
    int count = 0; // 初始化逆序对计数器
    if (l < r) {
        int mid = (l + r) / 2; // 计算中点
        // 递归地对左右子数组进行排序,并计算逆序对
        count = count + mS(a, l, mid);
        count = count + mS(a, mid + 1, r);
        // 合并两个子数组,并计算逆序对
        count = count + merge(a, l, mid, r);
    }
    return count; // 返回逆序对总数
}

signed main() {
    int n;
    cin >> n; // 读取序列长度
    vector<int> a(n); // 创建序列数组
    for (int i = 0; i < n; i++) {
        cin >> a[i]; // 读取序列元素
    }
    int vi = mS(a, 0, n - 1); // 调用 mS 函数计算逆序对
    cout << vi << endl; // 输出逆序对的数量
}

文章来源:https://blog.csdn.net/lcc1737/article/details/135432309
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。