#C. Challenging Cliffs

    远端评测题 2000ms 256MiB

Challenging Cliffs

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

挑战悬崖

题目描述

你是一位游戏设计师,你想要制作一条障碍赛道。其中玩家从左向右行走。

你已经选择了 nn 个山峰的高度,你希望将它们排列起来,使得第一个山峰和最后一个山峰的高度之差的绝对值尽可能小。

此外,你希望让游戏更具挑战性,由于上坡或平地行走比下坡行走更困难,因此关卡的难度将是山峰 ii 的数量(1i<n1 \leq i < n),使得 hihi+1h_i \leq h_{i+1},其中 hih_i 是第 ii 座山峰的高度。你不想浪费任何一个你建模的山峰,所以你必须全部使用它们。

从所有最小化 h1hn|h_1-h_n| 的排列中,找到一个最困难的。如果有多个顺序满足这些要求,您可以找到任何一个。

输入格式

第一行将包含一个整数 tt1t1001 \leq t \leq 100)——测试用例的数量。然后是 tt 个测试用例。

每个测试用例的第一行包含一个整数 nn2n21052 \leq n \leq 2 \cdot 10^5)——山峰的数量。

每个测试用例的第二行包含 nn 个整数 h1,,hnh_1,\ldots,h_n1hi1091 \leq h_i \leq 10^9),其中 hih_i 是第 ii 座山峰的高度。

保证所有测试用例中 nn 的总和不超过 21052 \cdot 10^5

输出格式

对于每个测试用例,输出 nn 个整数——给定高度按最大化所有最小化 h1hn|h_1-h_n| 的顺序中的难度得分的顺序排列。

如果有多个顺序满足这些要求,您可以输出任何一个。

样例 #1

样例输入 #1

2
4
4 2 1 2
2
3 1

样例输出 #1

2 4 1 2 
1 3

提示

在第一个测试用例中:

玩家从高度 22 开始,接下来上升到高度 44 ,难度增加了 11 。之后他会下降到高度 11 ,难度不变,因为他正在下坡。最后玩家会上升到高度 22 ,难度会增加 11 。起始高度和结束高度之间的绝对差等于 00 ,且最小。难度最大。

在第二个测试用例中:

玩家从高度 11 开始,接下来上升到高度 33 ,难度增加了 11 。起始高度和结束高度之间的绝对差等于 22 ,且最小,因为它们是唯一的高度。难度最大。

6.24下午1点半作业

未认领
状态
已结束
题目
6
开始时间
2023-6-26 0:00
截止时间
2023-7-10 23:59
可延期
24 小时