GESP2023年9月认证C++六级( 第三部分编程题（2）小杨的握手问题）

参考程序1（暴力枚举）

#include <iostream>
using namespace std;

int main() {
    int n = 0;
    cin >> n;  // 读入同学的数量

    int num[300000];  // 存储同学的学号
    for (int i = 0; i < n; i++) {
        cin >> num[i];  // 读入同学的进入顺序
    }

    long long handshakes = 0;  // 用来存储总握手次数

    // 暴力枚举：对每个同学，检查和之前已经进入的同学是否构成握手
    for (int i = 1; i < n; i++) {  // 从第二个同学开始
        for (int j = 0; j < i; j++) {  // 遍历当前同学之前已经进入的同学
            if (num[i] > num[j]) {  // 如果当前同学的学号小于已经在教室的同学
                handshakes++;  // 这两个同学会握手
            }
        }
    }

    cout << handshakes << endl;  // 输出握手的总次数
    return 0;
}

参考程序2（归并排序---逆序对）：

#include <iostream>
using namespace std;

int num[300000];  // 存储同学的学号
int tmp[300000];  // 临时数组，用来辅助归并排序

// 归并排序的修改版，用来计算逆序对
long long merge(int l, int r) {
    if (l + 1 == r)  // 如果区间只包含一个元素，则没有逆序对
        return 0;

    int m = (l + r) / 2;  // 找到中点
    long long res = merge(l, m) + merge(m, r);  // 分治：递归计算左右两部分的逆序对
    for (int i = l, j = m, k = l; k < r; k++) {
        if (j == r || (i < m && num[i] > num[j])) {
            tmp[k] = num[i];  // 如果左边元素小于右边元素，或右边元素已经处理完，则将左边元素放入临时数组
            i++;
        } else {
            tmp[k] = num[j];  // 否则将右边元素放入临时数组
            j++;
            res += m - i;  // 统计逆序对：如果左边元素大于右边元素，那么左边剩余的所有元素都与右边当前元素构成逆序对
        }
    }

    // 将临时数组的数据拷贝回原数组
    for (int k = l; k < r; k++)
        num[k] = tmp[k];

    return res;  // 返回当前区间的逆序对数
}

int main() {
    int n = 0;
    cin >> n;  // 读入同学的数量
    for (int i = 0; i < n; i++)  // 读入同学进入教室的顺序
        cin >> num[i];

    cout << merge(0, n) << endl;  // 计算并输出总的握手次数（即逆序对数）
    return 0;
}