#CF2218C. The 67th Permutation Problem
The 67th Permutation Problem
题目描述
到达学校后,Macaque 被他的朋友 AG-88301 相当粗暴地打招呼了。后者整晚都在喋喋不休地向一位毫无防备的陌生人讲述他关于 Collatz 猜想证明的开创性工作以及他第 次单恋,因此翘掉了作业。于是,像往常一样,AG-88301 以越来越少的感激或赞赏,让 Macaque 替他做作业。此时,Macaque 已经受够了,于是转向他的手下(你们!)来解决 AG-88301 的作业任务。
给定一个整数 。你需要构造一个长度为 的排列,使得将该排列划分为 个每段 个元素的连续块后,这些块的中位数之和最大化。
更形式化地,你需要构造一个长度为 的排列 ,使得 $\sum_{i=0}^{n-1}\operatorname{median}(a_{3i+1},a_{3i+2},a_{3i+3})$ 最大化。如果有多个可行的 ,输出任意一个即可。
长度为 的排列是由 到 的 个不同整数以任意顺序组成的数组。例如, 是一个排列,但 不是排列( 在数组中出现了两次), 也不是排列( 但数组中有 )。
包含 个元素的数组 的中位数是将 按非降序排序后第 个元素。
输入格式
每个测试包含多个测试用例。第一行包含测试用例的数量 ()。接下来是每个测试用例的描述。
每个测试用例的唯一一行包含一个整数 ()。
保证所有测试用例中 的总和不超过 。
输出格式
对于每个测试用例,输出一个排列 ,使得连续块的中位数之和最大化。如果有多个可行的 ,输出任意一个即可。
样例
3
2
1
3
1 3 4 2 5 6
3 1 2
5 2 4 8 3 9 7 1 6
说明
在第一个测试用例中, 是一个可行的答案,因为 $\operatorname{median}(1,3,4) + \operatorname{median}(2,5,6) = 3+5 = 8$,并且可以证明 是中位数之和的最大可能值。
在第二个测试用例中, 是一个可行的答案,因为当 时唯一可达的中位数之和为 。
相关
在下列比赛中: