逆序对计数问题

题目描述

逆序对（Inverse Pair）是序列中满足 ai > aj 且 i < j 的有序对的总数。给定一个正整数序列，计算其中的逆序对数目。这是一个典型的排序问题，常用来评估算法性能。

输入输出格式

输入参数

第一行：一个整数 n，表示序列的长度。

第二行：n 个正整数，表示给定的序列。

输出参数

输出逆序对的总数。

输入输出样例

输入样例#1

665 4 2 6 3 1

输出样例#1

说明

对于50%的数据，n ≤ 2500；对于100%的数据，n ≤ 40000。

解决方案

方法分析

逆序对计数问题可以通过多种算法高效解决，其中经典的方法是归并排序。归并排序的时间复杂度为 O(n log n)，适合处理较大的数据规模（n ≤ 40000）。

归并排序通过将数组分成两半，递归排序，然后合并过程中统计逆序对数目。具体来说：

如果两段的首元素顺序不正确，则所有左半部分的元素与右半部分的元素形成逆序对。

递归处理左右两部分，合并时记录逆序对数目。

代码实现

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int n, ans;int a[40002], t[40002];int merge_sort(int x, int y) {    if (y - x > 1) {        int mid = (x + y) / 2;        merge_sort(x, mid);        merge_sort(mid, y);                int p = x, q = mid;        while (p < mid || q >= y) {            if (q >= y || (p < mid && a[p] > a[q])) {                t[i++] = a[p++];                ans += mid - p;            } else {                t[i++] = a[q++];                ans += mid - p;            }        }                for (int i = x; i < mid; ++i) {            a[i] = t[i];        }    }}int main() {    // 读取输入    scanf("%d", &n);    scanf("%d %d %d %d %d %d", a, a+1, a+2, a+3, a+4, a+5);        // 调用归并排序计算逆序对数目    merge_sort(0, n);        cout << ans << endl;        return 0;}