Recamán 数列

题目描述

小杨最近发现了有趣的 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

AC Code：

#include<bits/stdc++.h>
int a[10000005];
int flag[10000005];
using namespace std;
int main (){
    int n;
    int i;
    cin>>n;
    if(n==-1)
        return 0;
    a[0]=0;
    memset(flag,0,sizeof(flag));
    for(i=1;i<=n;i++){
        if(a[i-1]-i>0 && !flag[a[i-1]-i])
            a[i]=a[i-1]-i;
        else
            a[i]=a[i-1]+i;
        flag[a[i]]=1;
    }
    sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	} 
    return 0;
}