简答题
偏难
#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
输出样例 1
输入样例 2
输出样例 2
样例解释
对于样例 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 <cstdio>
#include <algorithm>
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 < n; ++i) {
if (a[i] > a[i + 1]) {
flag = true;
int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
}
}
}
int main() {
scanf("%d", &n);
a[1] = 1;
vis[1] = 1;
for (int i = 2; i <= n; i++) {
if (a[i - 1] - i <= 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 <= n; i++)
printf("%d%c", a[i], " \n"[i == n]);
return 0;
}</pre>
这道题暂未补解析。