4660: 【GESP2412四级】Recamán数列

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

小样最近发现了有趣的 Recamán 数列，这个数列是这样生成的：
数列的第一项$a_1$ 是$1$ ；
如果$a_{k-1}-k$ 是正整数并且没有在数列中出现过，那么数列的第$k$ 项$a_k$ 为$a_{k-1}-k$ ，否则为$a_{k-1}+k$ 。
小杨想知道 Recamán 数列的前$n$ 项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。

输入

第一行，一个正整数$n$ 。

输出

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

样例输入 复制 

5

样例输出 复制 

1 2 3 6 7

提示

#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;
}

来源/分类

提交提交记录统计露一手!