题解：CF2048B Kevin and Permutation

lailai0916 · 2024-12-21 14:30:36 · 题解

题意简述

构造一个长度为 n 的排列，最小化所有长度为 k 的子区间的最小值之和。

解题思路

考虑每个长度为 k 的子区间的最小值对结果的影响。为了最小化所有子区间的最小值之和，我们可以采取以下策略：

• 从最小的数 1 开始，将 1 放置在位置 k，这样前 k 个区间的最小值为 1。
• 接着考虑数 2，将 2 放置在位置 2k，这样接下来的 k 个区间的最小值为 2。
• 依此类推，将数 x 放置在位置 xk，使得每个位置上的数尽可能影响到最少的区间，从而最小化区间的最小值之和。

对于剩下的数，可以随意放置，因为它们的放置不会影响已经确定的最小值。

参考代码

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

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