Recamán 数列题解

题目分析

本题要求生成 Recamán 数列的前 $n$ 项，并将这些项从小到大排序后输出。数列的生成规则如下：

• 第一项 $a_1 = 1$；
• 对于第 $k$ 项（$k \ge 2$）：
  • 记 $candidate = a_{k-1} - k$；
  • 如果 $candidate$ 是正整数且从未在数列中出现过，则 $a_k = candidate$；
  • 否则 $a_k = a_{k-1} + k$。

我们需要按照这个规则计算出前 $n$ 项，然后排序输出。题目保证 $n \le 3000$，时间限制为 1000 ms，内存限制为 256 MB。

解题思路

本题可以分为两个独立的步骤：

1. 生成数列
   按照规则逐项计算。我们需要快速判断一个数是否已经在数列中出现过。本题中 $n \le 3000$，数列中的数值不会太大（参考代码中假设最大值不超过 $10^6$），因此可以直接使用一个布尔数组 vis 记录某个数是否出现过，这样查找的时间复杂度为 $O(1)$。
   从 $a_1 = 1$ 开始，标记 vis[1] = true。对于 $i$ 从 $2$ 到 $n$，计算 $a_{i-1} - i$，如果该值大于 $0$ 且未被标记，则 $a_i$ 取该值；否则取 $a_{i-1} + i$。最后将 $a_i$ 标记为已出现。

2. 排序输出
   生成完数列后，对数组的前 $n$ 个元素进行排序。由于 $n \le 3000$，即便使用 $O(n^2)$ 的冒泡排序也足以在时限内完成（$3000^2 = 9 \times 10^6$ 次比较和交换完全可接受）。当然，可以直接使用标准库中的 sort 函数将复杂度降为 $O(n \log n)$，但参考代码中给出了一个手写的冒泡排序实现，这里会一并讲解。

算法说明

下面结合 C++ 参考代码详细说明每一步。

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4const int N = 2e5 + 5;
5const int C = 1e6 + 5;
6int n;
7int a[N];
8int vis[C];
9
10void bubble_sort(int *a, int n) {
11    bool flag = true;
12    while (flag) {
13        flag = false;
14        for (int i = 1; i < n; ++i) {
15            if (a[i] > a[i + 1]) {
16                flag = true;
17                int t = a[i];
18                a[i] = a[i + 1];
19                a[i + 1] = t;
20            }
21        }
22    }
23}
24
25int main() {
26    scanf("%d", &n);
27    a[1] = 1;
28    vis[1] = 1;
29    for (int i = 2; i <= n; i++) {
30        if (a[i - 1] - i <= 0 || vis[a[i - 1] - i])
31            a[i] = a[i - 1] + i;
32        else
33            a[i] = a[i - 1] - i;
34        vis[a[i]] = 1;
35    }
36    bubble_sort(a, n);
37    for (int i = 1; i <= n; i++)
38        printf("%d%c", a[i], " \n"[i == n]);
39    return 0;
40}

数组大小设计

• a[N]：存储数列，N = 2e5 + 5，实际只需要 $n+5$ 的大小，但开大一些更安全。
• vis[C]：标记某个数字是否出现过，C = 1e6 + 5。数列在 $n=3000$ 时产生的最大值不会超过 $1e6$（实际数值远小于该上限），因此数组足够容纳。

数列生成过程

1. 初始化 a[1] = 1，vis[1] = 1；
2. 循环 i 从 $2$ 到 $n$：
   • 判断 a[i-1] - i <= 0：如果该值不是正整数（$\le 0$），必须执行加法；
   • 或者 vis[a[i-1] - i] 为真（已经出现过），同样执行加法；
   • 其他情况执行减法；
3. 计算出的 a[i] 在 vis 数组中标记为出现。

这一过程直接模拟了题目规则，每步操作都是 $O(1)$ 的。

排序部分

参考代码提供了一个冒泡排序的实现 bubble_sort：

• 使用一个标志 flag 表示本轮是否发生了交换；
• 每次从 $1$ 到 $n-1$ 扫描相邻元素，逆序则交换并置 flag = true；
• 当一轮扫描没有交换时，说明数组已有序，排序结束。

因为 $n \le 3000$，冒泡排序的最坏时间复杂度为 $O(n^2)$，在本题中完全可行。

输出格式

printf("%d%c", a[i], " \n"[i == n]); 巧妙地控制了分隔符：不为最后一个元素时输出空格，最后一个元素输出换行。

时间复杂度分析

• 生成数列：循环 $n-1$ 次，每步 $O(1)$，总复杂度 $O(n)$；
• 标记与判断：直接数组下标访问，$O(1)$；
• 冒泡排序：$O(n^2)$；
• 总时间复杂度：$O(n^2)$。对于 $n \le 3000$，运算量约为 $9 \times 10^6$，可以在 1000 ms 内轻松完成。

如果使用标准 sort 函数，时间复杂度可优化为 $O(n \log n)$，但本题数据规模不需要。

代码优化建议

虽然参考代码的冒泡排序足以通过，但为了养成良好的编程习惯，推荐使用 C++ STL 中的 sort 替代手写冒泡排序：

cpp
复制
1sort(a + 1, a + 1 + n);

这样仅需一行即可完成排序，且时间复杂度更优。完整简化版代码就不再赘述，读者可以自行替换。

总结

本题考察了对数列递推规则的理解和模拟能力，以及基础的排序操作。难点在于正确判断减法条件（正整数且未出现过）并使用高效的方法记录状态。对于 $n \le 3000$ 的数据规模，即使使用 $O(n^2)$ 排序也能轻松通过。希望读者通过本题进一步熟悉数组标记法和排序算法的应用。