基于分治法计算两条平行线上端点的n条线段交点数的代码纠错及解决方案求助

首先得明确，这个问题的本质其实是求逆序数：当我们把下方直线y=0上的点按x坐标从小到大排序后，对应的上方y=1上的点的顺序如果出现逆序，每一对逆序就对应两条线段相交。所以核心就是用分治法求这个序列的逆序数。

接下来看你的代码里的几个关键问题：

• 所有vector参数都是传值而非引用：比如merge1、mergeSort1、merge2、mergeSort2里的vector< pair <int, int> > vect都是传值，这意味着你所有的排序和合并操作都是在vector的副本上进行的，原vector完全没被修改！比如mergeSort1执行完后，main里的vect还是初始顺序，这直接导致后续计算逆序数的基础就错了。
• 逆序数计算错误：merge2里的inv_count += (m - i)是错的，应该是inv_count += (n1 - i)——因为左半部分还有n1 - i个元素都比当前右半部分的元素大，每个都会产生一个逆序对。
• merge2的调用参数错误：mergeSort2里调用merge2(vect, l, m + 1, r)是不对的，应该是merge2(vect, l, m, r)，因为左半部分是l到m，右半部分是m+1到r，合并的范围是l到r，中间分界是m。
• 冗余的mergeSort1函数：其实我们可以直接用标准库的sort函数按pair的first元素排序，比自己写的mergeSort1更高效也不容易出错。

下面是修正后的完整代码：

#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;

// 合并两个子数组并计算逆序数，传引用修改原数组
int merge(vector<pair<int, int>>& vect, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int inv_count = 0;
    vector<pair<int, int>> left(n1);
    vector<pair<int, int>> right(n2);

    for (int i = 0; i < n1; i++)
        left[i] = vect[l + i];
    for (int j = 0; j < n2; j++)
        right[j] = vect[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (left[i].second <= right[j].second) {
            vect[k] = left[i];
            i++;
        } else {
            vect[k] = right[j];
            j++;
            // 左半部分剩余的n1-i个元素都比当前right[j]大，产生逆序对
            inv_count += n1 - i;
        }
        k++;
    }

    while (i < n1) {
        vect[k] = left[i];
        i++;
        k++;
    }
    while (j < n2) {
        vect[k] = right[j];
        j++;
        k++;
    }
    return inv_count;
}

// 分治求逆序数，传引用
int mergeSort(vector<pair<int, int>>& vect, int l, int r) {
    int inv_count = 0;
    if (r > l) {
        int m = l + (r - l) / 2;
        inv_count += mergeSort(vect, l, m);
        inv_count += mergeSort(vect, m + 1, r);
        inv_count += merge(vect, l, m, r);
    }
    return inv_count;
}

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> vect;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        vect.emplace_back(a, b);
    }

    // 按下方点的x坐标排序（pair默认先排first）
    sort(vect.begin(), vect.end());

    // 计算上方点序列的逆序数，就是交点数
    cout << mergeSort(vect, 0, n - 1) << endl;
    return 0;
}

测试你给的示例输入：3 1 101 -234 234 567 765，输入解析是n=3，然后三个点对：(1,101)、(-234,234)、(567,765)。排序后下方点的顺序是-234、1、567，对应的上方点是234、101、765，这个序列的逆序数是1（234>101），所以输出1，和预期一致。

内容的提问来源于stack exchange，提问作者Lily