【正经题解】字符排序

怎么说呢，这 $\LaTeX$ 真好看，爆了。
最近开始用 vector 了，真好用。

---

可以看见 $n \leq 3000$ ，那么大致推算一下， $a_n$ 肯定不会超过 $10^7$。 所以我们定义一个桶（vis），用来判断是否出现过。
那么考虑递推。先标记好 $a_1$。判断当 $a_{i-1}-k$ 是正整数时，并且借助桶来判断其是否已经出现。当同时满足这两个条件时我们定义 a[i]=a[i-1]-i 。否则任何一种情况我们都将其定义为 a[i]=a[i-1]+i ^[1]。那么注意要排序，输出要带空格。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7;
vector<int> a;//储存这个数列
vector<bool> vis(N,false);//桶
signed main(){
    int n;
    cin >> n;
    a.resize(3005);
    a[1]=1;
    vis[1]=1;
    for(int i=2;i<=n;i++){
        if(a[i-1]-i>0){//如果没出现过且为正整数
            if(vis[a[i-1]-i]!=1){
                a[i]=a[i-1]-i;//第 i 项为 a[i-1]-i
            }else{//出现过了
                a[i]=a[i-1]+i;
            }
        }else{//不是正整数
            a[i]=a[i-1]+i;
        }vis[a[i]]=1;//入桶，标记
    }sort(a.begin()+1,a.begin()+1+n);
    for(int i=1;i<=n;i++)cout << a[i] << " ";
    return 0;
}    

时间复杂度 $O(n+n \log n)$。其中 $O(n)$ 为递推复杂度， $O(n \log n)$ 为排序复杂度。但注意，本代码常数并不小，只是在 $n \leq 3000$ 的情况下没有问题。
空间复杂度 $O(n)$

---

1. 这里的 $i$ 既文中的 $k$ ↩︎