A29895. Recamán
填空题
较难
知识点
题目描述
Recamán
题目描述
小杨最近发现了有趣的 Recamán 数列，这个数列是这样生成的：
数列的第一项a1是 1；
如果ak-1 -k 是正整数并且没有在数列中出现过，那么数列的第 k 项 为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参考答案
#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;
}
上一题
下一题