简答题 偏难
#20726

Recamán 时间限制:1.0 s 内存限制:512.0 MB 题目描述 小杨最近发现了有趣的 Recamán 数列,这个数列是这样生成的: 数列的第一项 a…

Recamán

时间限制:1.0 s

内存限制:512.0 MB

题目描述

小杨最近发现了有趣的 Recamán 数列,这个数列是这样生成的:

数列的第一项 a1是 1 ;

如果 ak−1−k 是正整数并且没有在数列中出现过,那么数列的第 k 项 ak为 ak−1−k,否则为 ak−1+k。

小杨想知道 Recamán 数列的前 n 项从小到大排序后的结果。手动计算非常困难,小杨希望你能帮他解决这个问题。

输入格式

第一行,一个正整数 n 。

输出格式

一行,n 个空格分隔的整数,表示 Recamán 数列的前 n 项从小到大排序后的结果。

输入样例 1

5

输出样例 1

1 2 3 6 7

输入样例 2

8

输出样例 2

1 2 3 6 7 12 13 20

样例解释

对于样例 1,n=5 :

a1=1;

a1−2=−1,不是正整数,因此 a2=a1+2=3;

a2−3=0,不是正整数,因此 a3=a2+3=6;

a3−4=2,是正整数,且没有在数列中出现过,因此 a4=2;

a4−5=−3,不是正整数,因此 a5=a4+5=7;

a1,a2,a3,a4,a5从小到大排序后的结果为 1 2 3 6 7 。

数据范围

对于所有数据点,保证 1≤n≤3000。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; const int N = 2e5 + 5; const int C = 1e6 + 5; int n; int a[N]; int vis[C]; void bubble_sort(int *a, int n) { bool flag = true; while (flag) { flag = false; for (int i = 1; i &lt; n; ++i) { if (a[i] &gt; a[i + 1]) { flag = true; int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; } } } } int main() { scanf("%d", &amp;n); a[1] = 1; vis[1] = 1; for (int i = 2; i &lt;= n; i++) { if (a[i - 1] - i &lt;= 0 || vis[a[i - 1] - i]) a[i] = a[i - 1] + i; else a[i] = a[i - 1] - i; vis[a[i]] = 1; } bubble_sort(a, n); for (int i = 1; i &lt;= n; i++) printf("%d%c", a[i], " \n"[i == n]); return 0; }</pre>
这道题暂未补解析。