题解 | #游游的排列构造#

题目链接

游游的排列构造

题目描述

给定整数 $n$ 和 $k$ ，需要构造一个长度为 $n$ 的排列（包含 $1$ 到 $n$ 每个整数恰好一次），使得该排列中恰好有 $k$ 个“好元素”，并且任意两个好元素都不相邻。

一个元素被称为“好元素”，如果它是其所在前缀的最大值。

解题思路

这是一个构造题，我们需要找到一种系统性的方法来构建满足条件的排列。

首先，我们来分析“好元素”的性质：

排列的第一个元素 $p_1$ 永远是一个好元素。
如果 $p_i$ 是一个好元素，那么它必须大于所有在它之前的元素（ $p_j$ for $j < i$ ）。
因此，排列中的所有好元素构成一个严格递增的子序列。

接下来，分析“不相邻”的约束：

如果 $p_i$ 是一个好元素，那么 $p_{i+1}$ 不能是好元素。
这意味着 $p_{i+1}$ 必须小于其前缀的最大值，即 $p_{i+1} < \max(p_1, \dots, p_i)$ 。因为 $p_i$ 是好元素，所以这个条件等价于 $p_{i+1} < p_i$ 。
简单来说，每个好元素的后面必须紧跟着一个比它小的元素，这个小元素起到“隔离”的作用，防止下一个元素也成为好元素。

基于以上分析，我们可以设计一个清晰的构造策略：

分配角色：为了简化构造，我们预先决定哪些数字将扮演“好元素”的角色，哪些扮演“非好元素”的角色。一个自然的选择是：
- 让最大的 $k$ 个数字 $\{n-k+1, n-k+2, \dots, n\}$ 成为好元素。
- 让最小的 $n-k$ 个数字 $\{1, 2, \dots, n-k\}$ 成为非好元素。
交错放置：为了满足不相邻的约束，我们在排列的开头部分将好元素和非好元素交错放置。我们按从小到大的顺序使用这两组数。
- 放置第 1 个好元素（ $n-k+1$ ）和第 1 个隔离的非好元素（ $1$ ）。
- 放置第 2 个好元素（ $n-k+2$ ）和第 2 个隔离的非好元素（ $2$ ）。
- ...
- 这个过程持续 $k-1$ 次，放置了 $k-1$ 个好元素和 $k-1$ 个非好元素。
- 然后，放置第 $k$ 个（也是最后一个）好元素（ $n$ ）。
这样，排列的前 $2k-1$ 个位置就被填充为： $[n-k+1, 1, n-k+2, 2, \dots, n-1, k-1, n]$
填充剩余：将剩下的非好元素 $\{k, k+1, \dots, n-k\}$ 按升序填充到排列的剩余位置中。

正确性验证：

好元素数量：我们放置的 $k$ 个大数 $n-k+1, \dots, n$ 都在递增，并且每次都被放在一个比之前所有数都大的位置，所以它们都成为了好元素。而所有非好元素都比它们左侧最近的好元素要小，因此它们不会成为好元素。最后填充的数字也都小于排列中已经出现的 $n$ ，所以也不会成为好元素。总共恰好是 $k$ 个。
不相邻：通过交错放置，每个好元素（除了最后一个）后面都跟着一个非好元素，所以它们不相邻。
排列：该构造方法使用了 $1$ 到 $n$ 之间的所有整数，每个恰好一次，构成了一个有效的排列。

这种构造方法逻辑清晰，且能保证生成一个符合所有条件的解。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> p(n);
    int good_val = n - k + 1;
    int non_good_val = 1;

    // 交错放置 k-1 个好元素和 k-1 个非好元素
    for (int i = 0; i < k - 1; ++i) {
        p[2 * i] = good_val++;
        p[2 * i + 1] = non_good_val++;
    }

    // 放置第 k 个好元素
    p[2 * (k - 1)] = good_val++;

    // 填充剩余的非好元素
    for (int i = 2 * k - 1; i < n; ++i) {
        p[i] = non_good_val++;
    }

    for (int i = 0; i < n; ++i) {
        cout << p[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] p = new int[n];
        int goodVal = n - k + 1;
        int nonGoodVal = 1;

        // 交错放置 k-1 个好元素和 k-1 个非好元素
        for (int i = 0; i < k - 1; i++) {
            p[2 * i] = goodVal++;
            p[2 * i + 1] = nonGoodVal++;
        }

        // 放置第 k 个好元素
        p[2 * (k - 1)] = goodVal++;

        // 填充剩余的非好元素
        for (int i = 2 * k - 1; i < n; i++) {
            p[i] = nonGoodVal++;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(p[i]).append(i == n - 1 ? "" : " ");
        }
        System.out.println(sb.toString());
    }
}

def solve():
    n, k = map(int, input().split())
    
    p = [0] * n
    good_val = n - k + 1
    non_good_val = 1
    
    # 交错放置 k-1 个好元素和 k-1 个非好元素
    for i in range(k - 1):
        p[2 * i] = good_val
        good_val += 1
        p[2 * i + 1] = non_good_val
        non_good_val += 1
        
    # 放置第 k 个好元素
    p[2 * (k - 1)] = good_val
    
    # 填充剩余的非好元素
    for i in range(2 * k - 1, len(p)):
        p[i] = non_good_val
        non_good_val += 1
        
    print(*p)

solve()

算法及复杂度

算法：构造法。通过一次遍历，按照预设的逻辑填充数组来构造满足条件的排列。
时间复杂度：我们需要填充一个长度为 $n$ 的数组，每个位置计算一次。因此，总时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：我们需要一个长度为 $n$ 的数组来存储构造的排列。因此，空间复杂度为 $\mathcal{O}(n)$ 。