C++实现使用分治法的思想解决寻找逆序对数量的问题

题目：
给定一个长度为 $N$ 的 $int$ 型数组 $a[0,1,2,...,N-1]$，当 $i<j$ 且 $a[i]>a[j]$ ，则称 $a[i]$ 与 $a[j]$ 是一对逆序对。求该数组的逆序对数量。

思路：
题目的意思可以简单理解为：如果数组中有一个大数在小数前面，这就是一个逆序对。显然这是一个涉及到排序的问题，我们可以借助归并排序（利用了分治法）来解决该问题，原理如下。

在归并排序中，我们会得到排序好的左右子数组，虽然左右子数组中的元素的顺序发生了变化，但是左子数组中的元素在原数组的位置不管怎样都是在右子数组中的左边的。这也就意味着，我们在归并的时候，如果左子数组中出现了比右子数组中某一个元素 $R[j]$ 大的元素 $L[i]$，那么这两个元素就是一对逆序对。而且，左子数组剩余元素都可以与之右数组当前元素 $R[j]$ 构成逆序对，因为左子数组剩余元素肯定都比 $L[i]$ 大！

变种题目：
一长方形电路板两长边分别有 $n$ 个焊点，分别记作 $1,2,...,n$。现需要将一边的焊点与另一边的焊点用导线相连，共需要 $n$ 条导线连接 $n$ 对焊点。我们用 $(i,x_i)$ 来表示一根导线的连接方式，即一边的第 $i$ 点与另一边的第 $x_i$ 相连。两条导线 $(i,x_i)$ 和 $(j,x_j)$ 交叉，当 $i<j$ 且 $xi>xj$，或者 $i>j$ 且 $xi<xj$。
当给定焊点的连接方式时，请设计一分治算法计算有交叉点的个数。

解法：其实从交叉条件就可以知道是求逆序对数量了，上述思路完全适用（甚至将下面的代码一摸一样提交上去就可以）。

代码：

//
// main.cpp
// InversePairNumber
//
// Created by 胡昱 on 2021/11/1.
//

#include <iostream>
using namespace std;

// 借用归并排序算法实现分治法求数组的逆序对个数
int* computeInversePairNum(int* a, int n, int* ipn) {
    
    
    if (n == 1) {
    
        return a;
    }
    
    // 划分子问题（即划分为左右两个长度基本一致的数组）
    int leftMid = (0 + n - 1) / 2;
    int rightMid = (0 + n - 1) / 2 + 1;
    
    // 计算子问题长度
    int leftA_length = leftMid - 0 + 1;
    int rightA_length = n - rightMid;
    
    // 构建并拷贝数组
    int* leftA = new int[leftA_length];
    int* rightA = new int[rightA_length];
    for (int i = 0; i < leftA_length; ++i) {
    
        leftA[i] = a[i];
    }
    for (int i = leftA_length; i < n; ++i) {
    
        rightA[i - leftA_length] = a[i];
    }
    
    // 解决子问题（对左右两个子数组进行归并排序）
    leftA = computeInversePairNum(leftA, leftA_length, ipn);
    rightA = computeInversePairNum(rightA, rightA_length, ipn);
    
    // 合并子问题
    // 因为我们已经知道 leftA 和 leftB 两个数组已经是从小到大排好序的数组，因此可以很简单地找出逆序对
    for(int i = 0, leftA_index = 0, rightA_index = 0; i < n; ++i) {
    
        
        // 左数组跑空
        // 该情况下已经不可能构成逆序对，无须处理逆序对个数
        if (leftA_index >= leftA_length) {
    
            
            a[i] = rightA[rightA_index];
            ++rightA_index;
            continue;
        }
        
        // 右数组跑空
        // 该情况下已经不可能构成逆序对，无须处理逆序对个数
        if (rightA_index >= rightA_length) {
    
            
            a[i] = leftA[leftA_index];
            ++leftA_index;
            continue;
        }
        
        // 左数组当前元素大于右数组当前元素
        // 只有这种情况需要处理逆序对个数，即左数组剩余元素（包括当前）都可以与右数组当前元素构成逆序对
        // 故逆序对个数需要增加左数组剩余元素个数
        if (leftA[leftA_index] > rightA[rightA_index]) {
    
            
            (*ipn) += (leftA_length - leftA_index);
            
            a[i] = rightA[rightA_index];
            ++rightA_index;
        }
        
        // 左数组当前元素小于等于于右数组当前元素
        // 不符合逆序对定义，因此无须处理逆序对个数
        else {
    
            
            a[i] = leftA[leftA_index];
            ++leftA_index;
        }
    }
    
    // 释放空间并返回
    delete [] leftA;
    delete [] rightA;
    return a;
}

int main(int argc, const char * argv[]) {
    
    
    // 共m个问题
    int m;
    cin >> m;
    
    // 新建逆序对个数数量对象
    int* ipn = new int(0);
    
    while((--m) >= 0) {
    
        
        // 初始化逆序对个数
        *ipn = 0;
        
        // 输入数组长度
        int n;
        cin >> n;
        
        // 输入数组
        int* a = new int[n];
        for (int i = 0; i < n; ++i) {
    
            cin >> a[i];
        }
        
        // 开始归并排序
        a = computeInversePairNum(a, n, ipn);
        
        // 输出逆序对个数
        cout << *ipn << endl;
        
        // 释放空间
        delete [] a;
    }
    
    // 释放空间
    delete ipn;
}