#CF2048B. 凯文与排列
凯文与排列
B. Kevin 与排列
时间限制:每个测试用例 1 秒 内存限制:每个测试用例 256 MB
Kevin 是排列问题的高手。你正和 Kevin 在黑森林散步,闲暇时,他想向你提出如下问题。
给定两个正整数 和 ,构造一个长度为 的排列 ,使得所有长度为 的子数组 的最小值之和尽可能小。 形式化地说,你需要最小化:
$$\sum_{i=1}^{n-k+1}\left(\min_{j=i}^{i+k-1} p_j\right) $$长度为 的排列是一个由 到 这 个不同整数按任意顺序组成的数组。 例如 是一个排列,但 不是(数字 出现了两次), 也不是( 但数组中出现了 )。
数组 是数组 的一个子数组,如果 可以通过从 的开头删除若干(可以是 个或全部)元素、并从末尾删除若干(可以是 个或全部)元素得到。 如果删除元素的位置集合不同,则认为是不同的子数组。
输入格式
每个测试包含多组数据。 第一行一个整数 (),表示测试用例数量。
每组测试用例一行,包含两个整数 和 ()。
保证所有测试用例的 之和不超过 。
输出格式
对于每组测试用例,在一行输出 个整数 —— 即你构造的排列 。
如果有多种合法答案,输出任意一种即可。
样例输入
3
4 2
6 1
8 3
样例输出
3 1 2 4
5 2 1 6 4 3
4 6 2 8 3 1 5 7
样例说明
在第一个测试用例中,,考虑所有长度为 的子数组: 子数组 的最小值为 , 子数组 的最小值为 , 子数组 的最小值为 。 总和 是所有排列中最小的。
在第二个测试用例中,所有长度为 的子数组的最小值依次为 ,其和 可以证明是最小的。