语言月赛 202410 同桌
题目分析
- 有 $2n$ 个小朋友，编号 $1$ 到 $2n$；
- $n$ 张桌子，每张桌坐 $2$ 人；
- 每个小朋友 $i$ 希望和 $p_i$ 做同桌；
- 要判断是否存在一种配对，使得每对同桌 $(i, j)$ 满足：
- $p_i = j$ 且 $p_j = i$；
- 同桌不能是自己。
解题思路
- 将问题转化为检查每个同桌关系是否互相匹配；
- 遍历每个小朋友 $i$，检查：
- $p_i \neq i$，自己不能是同桌；
- $p_{p_i} = i$，对方也想和自己做同桌；
- 若所有小朋友均满足上述条件，则输出
Yes，否则输出 No。
处理流程
- 读入整数 $n$；
- 读入长度为 $2n$ 的数组 $p$；
- 对每个 $i$ 从 $1$ 到 $2n$：
- 如果 $p_i = i$，直接输出
No 并结束；
- 否则判断 $p_{p_i}$ 是否等于 $i$，不等则输出
No 并结束；
- 解析：$p_i$ 是 $i$ 希望的同桌。那么 $p_{p_i}$ 就是 $p_i$ 希望的同桌。
- 如果全部检查通过，输出
Yes。
复杂度分析
- 时间复杂度：$O(n)$，仅需一次遍历；
- 空间复杂度：$O(n)$，用于存储数组。
总结
- 题目核心在于双向匹配的检查；
- 只要每对同桌的需求是对称的，则答案是
Yes；
- 否则肯定是
No，直接排除；
- 算法简洁且效率高，适合 $n$ 最大 $5000$ 的情况。