B. Kevin and Permutation 题解

题意简述

给定 $n$ 和 $k$，构造一个 $1\sim n$ 的排列，使得所有长度为 $k$ 的连续子数组的最小值之和尽可能小。

思路分析

核心目标

要让总和最小，就要让小数字尽可能多地成为长度为 $k$ 的窗口的最小值。 一个小数字能覆盖多少个窗口，取决于它的位置：

• 把小数字每隔 $k$ 个位置放一个，就能让它在尽可能多的窗口中充当最小值。
• 大数字放在两个小数之间，不会成为任何窗口的最小值。

构造方法

1. 把数字分成 $k$ 组，每组依次填入小数，保证小数被窗口覆盖。
2. 大数放在中间位置，避免成为最小值。
3. 最终构造出的排列满足：小数分散、大数集中，最小值总和最小。

标准解法

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T, n, k, cnt;
    cin >> T;
    while (T--) {
        cin >> n >> k;
        cnt = n / k;
        for (int i = 1; i <= n; ++i) {
            cout << (i % k ? ++cnt : i / k) << " \n"[i == n];
        }
    }
    return 0;
}

代码解释

• cnt = n / k：初始分组基准值。
• i % k != 0：位置递增，填入更大的数。
• i % k == 0：重置为当前组的小数，保证小数被窗口覆盖。
• 该构造保证小数字出现在尽可能多的长度为 $k$ 的窗口中，从而总和最小。

复杂度分析

• 时间复杂度：$O(\sum n)$，线性构造。
• 空间复杂度：$O(1)$，直接输出不额外存数组。
• 满足题目限制：$t \le 10^3,\ \sum n \le 10^5$。

正确性说明

该构造方式是本题的经典贪心构造，能让每个小数覆盖尽可能多的窗口，且排列合法（数字不重复、恰好 $1\sim n$）。 满足题目“多解输出任意一个”的要求，可直接通过所有测试点。