自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:16:51，当前版本为作者最后更新于2024-12-14 14:54:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

欢迎报名洛谷网校，期待和大家一起进步！

本题考查桶思想和排序。

根据题目含义，先求出 Recamán 数列，使用数组 $a$ 进行存储。在求 Recamán 数列的时候，重点在于如何处理【没有在数列中出现过】。这里采用桶思想，定义数组 vis，如果 vis[x] == 1，说明 $x$ 这个数已经出现过了，否则没有出现过。至于 vis 数组应该开多少，后面会详细讨论这个问题。

因此我们可以写出下列计算 Recamán 数列的代码：

a[1] = vis[1] = 1;
for (int i = 2; i <= n; i++) {
    if (a[i - 1] - i >= 1 && !vis[a[i - 1] - i])
        a[i] = a[i - 1] - i;
    else
        a[i] = a[i - 1] + i;
    vis[a[i]] = 1;
}

题目要求输出 Recamán 数列从小到大排序后的结果。由于数据范围中 $n\leq 3000$，因此可以任意选择一种排序方式，例如选择排序、冒泡排序都是可以使用的。这里提供一个选择排序的参考代码：

for (int i = 1; i <= n; i++) {
    int mx = a[i], id = i;
    for (int j = i + 1; j <= n; j++) {
        if (a[j] < mx) {
            mx = a[j];
            id = j;
        }
    }
    swap(a[i], a[id]);
}

最后我们研究这个问题：记录这个数是否出现过的 vis 数组应该开多大呢？可以先将 vis 数组开得足够大（例如：$900$ 万），然后运行整个程序，输入 $3000$，可以看到最大的输出数字为 $11339$。因此，vis 数组不需要开的非常大，只需开到 $11340$ 即可。

实际上使用简单的数学推理即可得出，vis 数组肯定不需要开得很大。首先，只有执行加法时，最大值才会更新。假设一种最坏的情况（且是必然不可能出现的情况）：每一步都是执行加法，那么数列的第 $n$ 项的值是 $1+2+3+\dots+n=\dfrac{n(n+1)}{2}$，代入 $n=3000$ 得到结果为 $4501500$。这是一个相当宽松的上界，实际上，由于定义中优先选择减法生成新项，这会显著减缓数列的增长速度。总而言之，无需担心 vis 数组的大小会是一个天文数字。