Problem 1044. -- 聚友轩

1044: 聚友轩

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 5  Solved: 1
[Submit][Status][Web Board]

Description

今天是你的生日,你打算在聚友轩宴请你的八方好友。但是,你是一个pretty boy or hot girl,所以你有很多朋友,并且你的朋友大多互相不认识。这几天你在校内上看到一篇文章,说如果两个不认识的人在饭局上坐在一起,他们身高差距太大的话,互相会有很大的谈话压力,以至于出现冷场的局面。你可不愿自己的生日饭局上出现大面积冷场,你希望你的朋友们除了是你的朋友,也能成为对方的朋友。因此你打算自己给好友们排一次座位,使得相邻两人的身高差距都不会太大。
你预约的饭桌是聚友轩的大圆桌,朋友们将围着圆桌而坐,两两相临,你也坐在其中(虽然你认识每个好友,不会出现冷场现象,但是你也明显受到了身高压力的影响,希望能与自己身高相差无几的人坐在一起)。你通过各种隐蔽高深的小道消息和各种正大光明的强取明夺,终于弄清了每个好友的身高情况(当然你还去测量了自己的身高)。接着你需要安排朋友以及你自己的座位,使得任意相邻的两个人的身高差中差距最大的要尽量的小。这对你来说可不是一件轻松的任务,不过为了生日宴会的成功,你决定使出浑身解数来解决这个世纪难题(当然也许这根本就不是什么世纪难题^_^)。

Input

第一行,一个整数T,表示数据组数。
每组数据仅一行,若干个整数,表示你的每个朋友以及你自己的相对身高(即这些数值仅表示各人的相对高度,并不表示绝对身高值,因为你不希望朋友和你的身高泄露出去),相邻两数以一个空格隔开。
你宴请的好友数目的范围是2,50,所有相对身高值的范围是1,1000(当然你知道相对身高的单位不会是cm)。

Output

对于每组数据仅一行,排好座位后的按一定顺序排列的身高值,以一个空格隔开。如果有多种方案则输出字典序最小的结果(即保证该结果在所有可能结果中满足第一个人身高值最小,如若相等则满足第二个人身高值最小,如若相等则满足第三个人身高值最小,以此类推)。

Sample Input

2
1 2 3 4
1000 500 1

Sample Output

1 2 4 3
1 500 1000

HINT

第一个例子,最好把身高最矮和最高的两人分开,不要坐在一起。满足这个条件的方案都是最优方案,最小的最大身高差是2,其中字典序最靠前的方案是1 2 4 3。
第二个例子,只有三个人,所以无论怎么安排座位,一个人都会和剩余两个人相邻。字典序最靠前的方案是1 500 1000。

Source

[Submit][Status]