GESP 题解库 / 6 级题解 / [GESP202309 六级] 小杨的握手问题 · 第 21 / 27 题
GESP202309 六级 · B3874 · 中等

小杨的握手问题

统计"进入顺序"中的顺序对(非逆序对)数量。

📊
N ≤ 3 × 10⁵
同学数量
🔢
long long
计数结果
⚡
O(N log N)
时间复杂度
🎯
归并排序统计顺序对
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

N 名同学学号 0 ~ N−1,按给定顺序依次进入教室。每位同学进入时,要和已经在教室内、且学号小于自己的同学握手。求全班一共握手多少次。

💡
人话翻译:把"进入顺序"看成一个序列。对任意先进入的 i 和后进入的 j(i 在 j 前面),他们握手 ⟺ i 的学号小于 j 的学号。
所以答案就是序列中"顺序对"的个数(即前面小、后面大的配对),用归并排序(或树状数组)在 O(N log N) 内统计。

🔍 关键词提取

顺序对计数归并排序逆序对变体树状数组

已知条件

项目说明
输入第一行 N;第二行是进入顺序(学号排列)
输出握手总次数
数据范围2 ≤ N ≤ 3 × 10⁵
序列性质是 0 ~ N−1 的一个排列
答案可能很大最大可达 N(N−1)/2 ≈ 4.5 × 10¹⁰

需要解决的问题

02
思维导图
整理解题思路的全貌
🤝 先来的学号更小 ⟺ 顺序对
🧠 模型转化
按进入顺序排成序列 a
i 在 j 前且 a_i < a_j → 握手
所以答案是"顺序对"个数
与"逆序对"互为补集
📐 两种做法
做法一:直接统计顺序对
做法二:C(N,2) − 逆序对数
逆序对可用归并/BIT
答案一定相同
⚡ 归并排序
分治:左右两半各自排序
合并时若取左半元素,说明它更小
此时右半剩下的都更大 → 累加顺序对
O(N log N)
⚠️ 易错点
统计成逆序对(方向反了)
用 int 存答案(可达 4.5 × 10¹⁰)
归并写错导致漏计
N = 2 等边界
03
样例手算推导
样例的完整推演

🧮 样例 1:进入顺序 2 1 3 0,答案 2

逐个同学模拟一遍,同时用"顺序对"视角核对。

次序进入者学号教室内已有其中比它学号小的本次握手
12(空)—0
212无(1 < 2 不满足)0
331, 21、2 都小于 32
401, 2, 3无(0 最小)0

总计 2 ✓

1
用"顺序对"核对

序列 a = [2, 1, 3, 0]

所有 i < j 的配对,检查 a_i < a_j:

(2,1) → 2 > 1 ✗

(2,3) → 2 < 3 ✓

(2,0) → 2 > 0 ✗

(1,3) → 1 < 3 ✓

(1,0) → 1 > 0 ✗

(3,0) → 3 > 0 ✗

共 2 个 ✓

✅ 与模拟一致

🔑
注意这两组数据的关系:序列 [2,1,3,0] 的逆序对是 4 个((2,1)、(2,0)、(1,0)、(3,0)),顺序对是 2 个,4 + 2 = C(4,2) = 6 ✓。两者互补,所以也可以"统计逆序对再取补"。

🧮 样例 2:进入顺序 0 1 2 3 4 5,答案 15

学号递增入场,每个新来的学号都是教室里最大的,所以要跟所有人握手。

1
逐个统计

第 1 位(0):0 人

第 2 位(1):1 人

第 3 位(2):2 人

第 4 位(3):3 人

第 5 位(4):4 人

第 6 位(5):5 人

合计 0 + 1 + 2 + 3 + 4 + 5 = 15

✅ 15

2
用公式核对

这种情况所有配对都握手

总数 = C(6,2) = 6 × 5 / 2 = 15 ✓

✅ 一致

📊 三种情况对照

序列特点顺序对数量说明
严格递增C(N,2)(最大)人人都和所有人握手
严格递减0(最小)每次来的都是最小的,无人可握
随机排列介于两者之间期望约 C(N,2)/2
⚠️
注意这个"互补"关系:递增序列的顺序对是 C(N,2)、逆序对是 0;递减序列正好相反。
所以做题时一定要看清"谁来跟谁握手"的方向——题目说"和学号小于自己的同学握手",那就对应"顺序对"。如果理解成"和学号大于自己的握手",答案就完全反了。
04
解法对比
归并排序 vs 双重循环 / 树状数组

⚔️ 解法对比

🟢 归并排序统计(推荐) 推荐

分治合并时累计"顺序对"贡献

  • 时间 O(N log N)
  • N = 3 × 10⁵ 时约 6 × 10⁶
  • 代码 30 行
  • 题目提示里就推荐了它
💡
合并时的计数规则:当从左半取出一个元素时,说明它比右半剩余的元素都小,于是累加"右半剩余元素个数"到答案。这与统计逆序对的写法正好相反(那时取右半元素才累加)。

🟠 树状数组

从左到右扫描,用 BIT 查询"已出现且比当前小的个数"

  • 时间 O(N log N)
  • 代码更短(约 25 行)
  • 思路直接
  • 需要值域大小 N
⚠️
两种都很好:BIT 的写法是"边扫边查",更容易理解;归并排序不需要额外的树结构。题目提示推荐归并,但 BIT 同样正确。

📈 性能对比

方案复杂度代码量
归并排序O(N log N)约 30 行
树状数组O(N log N)约 25 行
双重循环O(N²) = 4.5 × 10¹⁰❌ 超时
05
算法流程图
归并排序中累计顺序对
开始读入 N 和进入顺序数组 a;ans = 0对区间做归并排序(分治)合并时,取的是左半元素还是右半元素?左半 ✓ans 加上"右半剩余元素个数"(它们都更大)右半 ✗直接把右半元素放入临时数组把临时数组拷回原区间所有分治层都合并完了吗?输出 ans继续合并
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🤝 握手总次数

输入进入顺序,程序用暴力法统计顺序对(演示规模内),并展示每位同学的握手次数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(归并排序统计顺序对)

#include <bits/stdc++.h>
using namespace std;

int a[300005], tmp[300005];
long long ans = 0;

void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] < a[j]) {
            // 取左半元素:它比右半"剩余"的都小,产生顺序对
            ans += (long long)(r - j + 1);
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (int t = l; t <= r; t++) a[t] = tmp[t];
}

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%d", &a[i]);

    mergeSort(0, N - 1);
    printf("%lld\n", ans);
    return 0;
}
🔑
为什么"取左半元素"时要累加 r − j + 1?因为此时右半还没被取走的元素是 a[j..r],它们都比 a[i] 大(因为两半各自有序),所以 a[i] 与这 r − j + 1 个元素都构成"顺序对"(左小右大)✓。
统计逆序对时恰好相反:那时是在"取右半元素"时累加 mid − i + 1。

📖 关键几行怎么看

代码作用为什么这样写
mergeSort(l, mid); mergeSort(mid+1, r);分治两半各自有序后才能线性合并
if (a[i] < a[j]) ans += r - j + 1;核心计数取左半 → 产生顺序对
else tmp[k++] = a[j++];取右半不产生顺序对(右元素不更大)
long long ans类型答案可达 4.5 × 10¹⁰,必须 long long
⚠️
四个坑:① 把顺序对统计成逆序对(应在"取左半"时累加);② 用 int 存答案;③ 忘记把临时数组拷回原数组(导致后续层出错);④ 递归深度(N = 3 × 10⁵ 时归并递归深度只有约 19 层,安全)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4
2 1 3 0
2题面样例 1
6
0 1 2 3 4 5
15题面样例 2
2
1 0
0先来学号 1,后来 0:0 不是更小,不握手
2
0 1
1先来 0,1 进来时学号更大 → 握手 1 次
3
2 1 0
0严格递减,无人握手
3
0 1 2
3严格递增,等于 C(3,2) = 3
✅
自查清单:① 统计的是顺序对吗?② 用 long long 吗?③ 复杂度 O(N log N) 吗?

🚨 易错点清单

⚠️
方向搞反:条件是"已入场且学号更小",对应顺序对,不是逆序对。
⚠️
用 int:答案最大约 4.5 × 10¹⁰,需 long long。
⚠️
暴力双重循环:N = 3 × 10⁵ 时会超时,需 O(N log N)。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N log N)
空间复杂度
O(N)
N 最大
3 × 10⁵
运算量
约 6 × 10⁶

时间怎么算的?

空间都用在哪?

需要与原数组等长的临时数组。

✅ 约 600 万次操作,瞬间完成。相比暴力枚举两两配对的 4.5 × 10¹⁰,快了四个数量级。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 归并排序统计"顺序对"(左小右大)
if (a[i] < a[j]) { ans += r - j + 1; tmp[k++] = a[i++]; }
else             { tmp[k++] = a[j++]; }

// 对照:统计"逆序对"(左大右小)
if (a[i] <= a[j]) { tmp[k++] = a[i++]; }
else              { ans += mid - i + 1; tmp[k++] = a[j++]; }

// 两者的关系
// 顺序对数 + 逆序对数 = C(N, 2)
// 所以统计出任意一个,另一个用总数减即可

// 用树状数组统计"已出现且更小"的个数
// for (i = 0..N-1) { ans += query(a[i] - 1); add(a[i], 1); }

// 归并排序还能顺便完成排序,一举两得

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
顺序对左小右大的配对握手、配对、正序关系计数
逆序对左大右小的配对排序最少交换次数、逆序统计
互补关系顺序对 + 逆序对 = C(N,2)两种统计互相验证
🌟
思考题:如果题目改成"和学号大于自己的同学握手",答案会变成什么?(提示:就变成逆序对了,而且此时"顺序对 + 逆序对 = C(N,2)",所以新答案是 C(N,2) − 原答案。同一道题,规则方向一改,答案就是互补的——读题时务必逐字看清。)