游游的排列构造

思路

这题要我们构造一个长度为 n 的排列，使得恰好有 k 个"好元素"（即前缀最大值），而且任意两个好元素不能相邻。

先想想好元素的性质：好元素就是从左往右扫的时候，每次遇到一个比之前所有值都大的位置。第一个位置一定是好元素（它自己就是前缀最大值）。

那怎么让好元素不相邻呢？最直觉的想法是把好元素放在偶数位置（第 1、3、5、... 个位置），这样相邻的两个好元素之间至少隔了一个非好元素。

具体构造方法：把 1 到 n 这些值分成 k 个块。

  • 前 k-1 个块，每块 2 个数：第 i 个块（0-indexed）包含 ，我们先输出大的 （作为好元素），再输出小的 （作为间隔）。
  • 最后一个块包含剩余所有值 ，先输出最大值 n（作为好元素），再依次输出剩下的。

为什么这样是对的？因为每个块的最大值都比前面所有块的所有值都大，所以它一定是前缀最大值。而块内其他元素都比当前块的最大值小，不可能成为新的前缀最大值。好元素之间都被至少一个非好元素隔开，满足不相邻的条件。

拿样例验证一下：n=5, k=2。

  • 块 0：{1, 2} → 输出 2 1
  • 块 1（最后）：{3, 4, 5} → 输出 5 3 4
  • 结果：2 1 5 3 4，好元素在位置 1 和 3，恰好 2 个且不相邻。

代码

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

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> ans;
    // 前 k-1 个块，每块输出 (大, 小)
    for (int i = 0; i < k - 1; i++) {
        ans.push_back(2 * i + 2);  // 好元素
        ans.push_back(2 * i + 1);  // 间隔
    }
    // 最后一个块：先输出 n（好元素），再输出剩余值
    ans.push_back(n);
    for (int v = 2 * (k - 1) + 1; v < n; v++) {
        ans.push_back(v);
    }
    for (int i = 0; i < n; i++) {
        printf("%d%c", ans[i], i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        // 前 k-1 个块，每块输出 (大, 小)
        for (int i = 0; i < k - 1; i++) {
            if (sb.length() > 0) sb.append(' ');
            sb.append(2 * i + 2);  // 好元素
            sb.append(' ');
            sb.append(2 * i + 1);  // 间隔
        }
        // 最后一个块：先输出 n（好元素），再输出剩余值
        if (sb.length() > 0) sb.append(' ');
        sb.append(n);
        for (int v = 2 * (k - 1) + 1; v < n; v++) {
            sb.append(' ');
            sb.append(v);
        }
        System.out.println(sb.toString());
    }
}

n, k = map(int, input().split())
ans = []
for i in range(k - 1):
    ans.append(2 * i + 2)
    ans.append(2 * i + 1)
ans.append(n)
for v in range(2 * (k - 1) + 1, n):
    ans.append(v)
print(' '.join(map(str, ans)))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const [n, k] = line.trim().split(' ').map(Number);
    const ans = [];
    for (let i = 0; i < k - 1; i++) {
        ans.push(2 * i + 2);
        ans.push(2 * i + 1);
    }
    ans.push(n);
    for (let v = 2 * (k - 1) + 1; v < n; v++) {
        ans.push(v);
    }
    console.log(ans.join(' '));
    rl.close();
});

复杂度分析

  • 时间复杂度: ，构造排列只需遍历一次。
  • 空间复杂度: ，存储结果数组。