Written by @Yue_chen

题意：

给定一个长度 n 和一个 k ；

我们必须构造一个长度为 n 的序列 a（序列的定义为 1~n 当且仅当出现一次），并且，该序列 |a[i] - i| >= k。

并且使字典序尽可能小。

思路：

答案唯一，一眼贪心。

当 k > n/2 时：

显然数组中间的数无论如何也没法满足|a[i] - i| >= k，直接输出-1。

当 k < n/2 时：

我们根据贪心发现，当 n >= 4*k时，（n, k）可以转移为(n - k*2, k)；

例如：

9 2                                5 2

3 4 1 2 7 8 9 5 6     ->   7 8 9 5 6

由于前2*k位满足贪心的最小字典序，k很小时，不论 n 多大时，前缀数组一定为 3 4 1 2。因此我们可以直接推出前缀固定的排列方式。

在上一步的化简之后，n 总会 < 4*k：

我们根据贪心方法手玩一下四个样例：

8 3

4 5 6 7 8 1 2 3

9 3

4 5 6 7 8 9 1 2 3

10 3

4 5 6 1 8 9 10 2 3 7

11 3

4 5 6 1 2 9 10 11 3 7 8

我们发现 当 n <= 3*k时：

将 [1 2 3 ... n-1 n] 循环左移k次，就是最终答案

当 3*k < n < 4*k 时：

出现了一种特殊的构造方式，我们尝试模拟一下这种构造方式；

实际上是先把最后k个数前移k次，再把前k个数后移k次，如果位置撞了，就顺延到后面的位置上，直到找到空位为止。

剩下的数依次从小到大找到一个空的位置。

时间复杂度O(n)

AC代码：

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
    int n, k; cin>>n>>k;
    
    vector<int> p(n+1);//答案数组
    
    int m = n/(2 * k);
    //初步判断
    if(m == 0) {
        cout<<"-1\n";
        return ;
    }
    
    //化简转移
    int j = 1;
    while(m > 1) {
        for(int i=j; i<j+k; ++i) {
            p[i] = i + k;
        }
        for(int i=j+k; i<j+2*k; ++i) {
            p[i] = i - k;
        }
        m--;
        j += 2*k;
    }
    
    //分讨构造
    int len = n-j+1;
    if(len > k*3) {
        //先放后k个
        for(int i=n-k,x=0; i>n-k-k; --i,x++) {
            p[i] = n-x;
        }
        //再放前k个
        for(int i=j+k,x=0; x<k and i<=n; i++) {
            if(!p[i]) {
                p[i] = j+x; x++;
            }
        }
        //最后总小到大依次放
        for(int i=j,x=j+k; i<=n; ++i) {
            if(!p[i]) {
                p[i] = x++;
            }
        }
    }else {
        //直接循环左移k次放
        for(int i=j; i<=n-k; ++i) {
            p[i] = i + k;
        }
        for(int i=n-k+1; i<=n; ++i) {
            p[i] = j + i - (n-k+1);
        }
    }
    
    for(int i=1; i<=n; ++i) {
        cout<<p[i]<<" \n"[i==n];
    }
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1; //cin>>t;
    while (t--) solve();
    return 0;
}