2021牛客寒假算法基础集训营1 I.限制不互素对的排列

题目链接

题目描述

输入一个数 $n$，请构造一个长度为 $n$ 的排列，使得其中正好有 $k$ 对相邻的数 $gcd$（最大公约数）大于 $1$ 。
排列是指 $1$ 到 $n$ 一共 $n$ 个数，每个数都出现过且仅出现过 $1$ 次。

输入描述:

两个整数 $n$ 和 $k$，用空格隔开。
$2\leq n\leq 100000,0\leq k \leq n/2$

输出描述:

如果不存在可行的构造方案，输出 $-1$。
否则输出一行 $n$ 个数，用空格隔开。如果有多组可行的构造方案，输出任意一组即可。

示例1

输入

2 1

输出

-1

示例2

输入

6 3

输出

5 3 6 2 4 1

题目限制了 $k\leq n/2$，这点非常关键，我就是没有意识到这一点卡了很久~
我们发现 $1-n$ 之间的偶数恰好是 $\frac{n}{2}$ 个，所以我们只需要排列这些偶数就能获得 $\frac{n}{2}-1$ 对，那么离最大目标还差一个，我们只需要抽一个 $6$ 出来和 $3$ 拼在一起就行，剩下的数按顺序输出即可，AC代码如下：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    int n, k;
    vector<int> v;
    set<int> s;
    cin >> n >> k;
    if (n < 6 && k == n / 2) {
        cout << "-1";
        return 0;
    }
    for (int i = 2; i <= n; i += 2) if (i != 6) v.push_back(i);
    v.push_back(6);
    v.push_back(3);
    for (int i = 0; i <= k; i++) cout << v[i] << " ", s.insert(v[i]);
    for (int i = 1; i <= n; i++) if (!s.count(i)) cout << i << " ";
    return 0;
}