小杨的握手问题 题解

题目分析

我们先理解握手的规则：全班同学按照一个给定顺序进入教室。每位同学进入时，需要和 已经在教室里 且 学号小于自己 的同学握手。我们要统计整个过程中全班握手的总次数。

设进入顺序为序列 $a_0, a_1, \dots, a_{N-1}$，其中 $a_i$ 表示第 $i$ 个进入教室的同学的学号。对于第 $i$ 个同学，他进入时教室里已有第 $0 \sim i-1$ 个同学。他需要和所有满足 $j<i$ 且 $a_j<a_i$ 的同学握手。

因此，全班握手总次数等于：

这实际上就是统计序列中 顺序对 的个数。顺序对是指下标小的元素值也小的情况，即 $j<i$ 且 $a_j<a_i$。这和常见的“逆序对”（$j<i$ 且 $a_j>a_i$）恰好相反。由于学号是 $0 \sim N-1$ 的一个排列，所有元素两两不同，不存在相等的情况。

解题思路

本题数据范围 $N \le 3 \times 10^5$，$O(N2)$ 的暴力枚举会超时，需要 $O(N \log N)$ 的算法。题目提示可以使用 归并排序进行降序排序，并在此过程中求解。

通常我们用归并排序可以统计逆序对，只需在归并时当左边元素大于右边元素时，将右边剩余的元素个数累加。本题要求的是顺序对，做法类似：对数组进行 降序归并排序，在归并过程中，当取走右边元素时，说明当前左边剩余的元素 都小于或等于 右边元素，且它们在原序列中位于右边元素之前，因此这些左边元素都与右边元素构成顺序对。由于学号互不相同，等于的情况不会发生，所以“小于或等于”就是“小于”。

降序归并统计顺序对的原理

假设我们要将数组 num[l..r-1] 按降序排序，并统计该区间内的顺序对数量。先将数组分成左右两半：[l, m) 和 [m, r)，递归处理两半，并得到各自内部产生的顺序对。然后合并两个已降序的子数组。

合并时，使用两个指针 i = l（左半当前元素）和 j = m（右半当前元素），依次比较：

• 如果 num[i] > num[j]，说明左半当前元素更大，按降序应放入临时数组，i 右移。
• 如果 num[i] ≤ num[j]，说明右半当前元素更大或相等（本题不相等，但算法兼容）。此时左半从 i 到 m-1 剩余的所有元素，在原序列中都位于 num[j] 的左边，且由于左半已降序，剩余的元素均 ≤ num[i] ≤ num[j]，也就是都小于 num[j]。因此这 m - i 个元素每个都能与 num[j] 组成一个顺序对。我们将 m - i 累加到总答案中，然后取走 num[j]，j 右移。

如此不断合并，就能在排序的同时统计出全部顺序对的数量。

算法说明

1. 输入与初始化
   读入 $N$ 和进入顺序数组 num[0..N-1]。准备一个同样大小的临时数组 tmp 用于归并。

2. 递归归并函数 merge(l, r)

   • 若区间长度小于等于1（l + 1 == r），返回 0（没有顺序对）。
   • 取中点 m = (l + r) / 2。
   • 递归计算左右两部分内部的顺序对：res = merge(l, m) + merge(m, r)。
   • 合并两个已降序的区间 [l, m) 和 [m, r)，同时统计跨越两部分的顺序对。
     • 用 i 从左半起点 l 开始，j 从右半起点 m 开始，k 从 l 开始填充 tmp。
     • 当 j == r 或 (i < m 且 num[i] > num[j]) 时，取左边元素填入 tmp，i++。
     • 否则，取右边元素填入 tmp，j++，并执行 res += m - i。
   • 将 tmp[l..r-1] 复制回 num 对应位置。
   • 返回 res。

3. 输出结果
   调用 merge(0, n) 得到总握手次数，输出即可。注意答案可能超过 32 位整数范围，需使用 long long 存储。

时间复杂度分析

• 归并排序的递归深度为 $O(\log N)$，每层合并操作需要遍历整个区间，花费 $O(N)$ 时间。
• 总时间复杂度为 $O(N \log N)$，可以应对 $N \le 3 \times 10^5$ 的数据规模。
• 空间复杂度为 $O(N)$，用于临时数组 tmp 和递归栈。

参考代码

cpp
复制
1#include <iostream>
2using namespace std;
3
4int num[300000];   // 原序列，同时也是被排序的数组
5int tmp[300000];   // 归并时的临时数组
6
7// 对区间 [l, r) 进行降序归并排序，并返回该区间内的顺序对总数
8long long merge(int l, int r) {
9    if (l + 1 == r)       // 区间长度为1，没有顺序对
10        return 0;
11    int m = (l + r) / 2;
12    long long res = merge(l, m) + merge(m, r);  // 左右两半内部的顺序对
13
14    // 合并两个降序区间，同时统计跨越两部分的顺序对
15    for (int i = l, j = m, k = l; k < r; k++) {
16        if (j == r || (i < m && num[i] > num[j])) {
17            // 左半部分当前元素更大，取左边
18            tmp[k] = num[i];
19            i++;
20        } else {
21            // 右半部分当前元素更大或相等，取右边
22            // 此时左半部分剩余元素均小于等于 num[j]，即组成 m - i 个顺序对
23            tmp[k] = num[j];
24            j++;
25            res += m - i;
26        }
27    }
28
29    // 将归并结果写回原数组
30    for (int k = l; k < r; k++)
31        num[k] = tmp[k];
32
33    return res;
34}
35
36int main() {
37    int n;
38    cin >> n;
39    for (int i = 0; i < n; i++)
40        cin >> num[i];
41
42    cout << merge(0, n) << endl;
43    return 0;
44}

代码解释

• merge(l, r) 函数处理区间 [l, r)（左闭右开），返回该区间内的顺序对数量。
• 当区间长度为 1 时直接返回 0。
• 将区间平分为 [l, m) 和 [m, r)，res 初始为左右两部分的顺序对之和。
• 合并时，i 指向左半部分，j 指向右半部分。if 条件判断何时取左边：右半耗尽，或者左半当前元素大于右半当前元素。
• 当取走右半元素时，意味着该元素与左半剩余的所有 m - i 个元素都构成顺序对（因为这些元素位置在它之前，且值更小），累加到 res。
• 最后将排好序的 tmp 复制回 num（保持降序），并返回 res。
• 主函数读入后直接调用 merge(0, n) 并打印结果。

小结

本题核心在于将握手次数转化为统计顺序对，并利用归并排序在 $O(N \log N)$ 时间内完成。理解归并过程中顺序对产生的时机（右边元素被取走时，左边剩余元素个数）是关键。该方法同样可以类比用于统计逆序对或其他偏序关系，是经典且必须掌握的技巧。