题解：CF2048B Kevin and Permutation

原题链接

• 洛谷 CF2048B Kevin and Permutation

题意简述

构造一个长度为 $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;
}