题目 | K Derangement

AtCoder Regular Contest 144

C - K Derangement

https://atcoder.jp/contests/arc144/tasks/arc144_c

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $600$ points

Problem Statement

You are given positive integers $N$ and $K$. Find the lexicographically smallest permutation $A=(A_1,A_2,\dots ,A_N)$ of the integers from $1$ through $N$ that satisfies the following condition:

• $|A_i-i|\ge K$ for all $i$ ($1\le i\le N$).

If there is no such permutation, print -1.

Constraints

• $2\le N\le 3\times {10}^5$
• $1\le K\le N-1$

---

Input

Input is given from Standard Input in the following format:

$N$ $K$

Output

Print the lexicographically smallest permutation $A=(A_1,A_2,\dots ,A_N)$ of the integers from $1$ through $N$ that satisfies the condition, in the following format:

$A_1$ $A_2$ $\dots$ $A_N$

If there is no such permutation, print -1.

---

Sample Input 1

3 1

Sample Output 1

2 3 1

Two permutations satisfy the condition: $(2,3,1)$ and $(3,1,2)$. For instance, the following holds for $(2,3,1)$:

• $|A_1-1|=1\ge K$
• $|A_2-2|=1\ge K$
• $|A_3-3|=2\ge K$

---

Sample Input 2

8 3

Sample Output 2

4 5 6 7 8 1 2 3

---

Sample Input 3

8 6

Sample Output 3

-1

---

解题笔记

首先需要找到存在这种排列的必要条件，即 $N\ge 2K$。因为第 $K$ 位要么取 $K-K=0$，要么取 $K+K=2K$，由于 $0$ 不符合题意，则第 $K$ 位必须取 $2K$。要满足这个条件，必须有 $N\ge 2K$。

接下来的重点就是找到通项公式。分为四种情况：

• $N<2K$: 无解

• $2K\le N\le 3K$:

  $$A(i)=\{\begin{array}{ll}i+K& (1\le i\le N-K)\\ i-N+K& (N-K<i\le N)\end{array}$$

• $3K<N\le 4K$:

  $$A(i)=\{\begin{array}{ll}i+K& (1\le i\le K)\\ i-K& (K<i\le N-2K)\\ i+K& (N-2K<i\le N-K)\\ i-2K& (N-K<i\le 3K)\\ i-K& (3K<i\le N)\end{array}$$

• $4K<N$:

  $$A(i)=\{\begin{array}{ll}i+K& (1\le i\le K)\\ i-K& (K<i\le 2K)\\ A(i)& (2K<i\le N)\end{array}$$

  这个意思是前 $2K$ 位为 $(K+1,\dots ,2K,1,\dots ,K)$，剩余的部分的 $N^{\prime }=N-2K$，再选择符合 $N^{\prime }$ 大小的公式。不断使用情况四的公式进行递推，一定可以转化为情况二或情况三。

代码

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    if (2 * K > N)
    {
        cout << -1 << endl;
        return 0;
    }
    int cnt = 0;
    while (N - cnt >= 4 * K)
    {
        for (int i = 1; i <= K; i++)
            cout << cnt + i + K << ' ';
        for (int i = 1; i <= K; i++)
            cout << cnt + i << ' ';
        cnt += 2 * K;
    }
    if (N - cnt <= 3 * K)
    {
        int i = 1;
        for (; i <= (N - cnt) - K; i++)
            cout << i + K + cnt << ' ';
        for (; i <= (N - cnt); i++)
            cout << i - (N - cnt) + K + cnt << ' ';
    }
    else
    {
        int i = 1;
        for (; i <= K; i++)
            cout << i + K + cnt << ' ';
        for (; i <= (N - cnt) - 2 * K; i++)
            cout << i - K + cnt << ' ';
        for (; i <= (N - cnt) - K; i++)
            cout << i + K + cnt << ' ';
        for (; i <= 3 * K; i++)
            cout << i - 2 * K + cnt << ' ';
        for (; i <= (N - cnt); i++)
            cout << i - K + cnt << ' ';
    }
    cout << endl;
    return 0;
}