788. 逆序对的数量

大佬教程收集整理的这篇文章主要介绍了788. 逆序对的数量，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

题目传送门

一、理解感悟

1、啥是逆序对？

2、咋求逆序对？

3、与归并排序有啥关系？

二、代码实现

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int n = 100010;
int n;    //n上数据
int q[n]; //原数组
int tmp[n];//临时数组
LL ans;//结果

/**
 * 功能：归并排序
 * @param q 原数组
 * @param l 左侧开始索引
 * @param r 右侧结束索引
 */
void merge_sort(int q[], int l, int r) {
    //数组为空，则是递归出口
    if (l >= r) return;
    //中位值
    int mid = l + r >> 1;
    //递归左侧
    merge_sort(q, l, mid);
    //递归右侧
    merge_sort(q, mid + 1, r);

    int i = l;       //左侧出发点
    int j = mid + 1; //右侧出发点
    int k = 0;       //下标索引
    //两个数组每个数据打擂台，谁小谁进入临时数组
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else {
            tmp[k++] = q[j++];
            //注意：这里有变化！
            //(1)这里进来一次，就表示出现了一回逆序的数字，
            //(2)因为两组PK的数组，本身自己内部是有序的，由小到大的。所以，当发现一个逆序时，
            // 此数字后面的其它数字必须也是逆序。此数字与它后面的数字的总个数=mid-i+1
            ans += mid - i + 1;
        }
    //如果有剩余的，就全部扫进临时数组
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    //将tmp数组数据复制回q数组
    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

int main() {
    //输入
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> q[i];
    //归并排序
    merge_sort(q, 1, n);
    //输出
    cout << ans << endl;
    return 0;
}

大佬总结

以上是大佬教程为你收集整理的788. 逆序对的数量全部内容，希望文章能够帮你解决788. 逆序对的数量所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。