TopCoder

Thumb %e6%88%aa%e5%9c%96 2020 07 24 %e4%b8%8b%e5%8d%8812.28.41
8e7
壓不贏$fhvirus$

User's AC Ratio

100.0% (19/19)

Submission's AC Ratio

63.2% (48/76)

Tags

Description

給一串數字h1,h2,h3,...,hn,這串數字的爛度定義成:

H = |h1-h2|+|h2-h3|+...+|hn-1-hn|

現在你要修改這串數字,使得爛度儘量小。

對於每個數字,你可以讓它和其它的任何數字交換,只能換一次,也可以不換。

找出每個數字分別該和哪個數字交換,才可以讓爛度最小。

Input Format

輸入的第一行有一個整數T,代表接下來有幾組測資。

每組測資的第一行有一個數N(N<1000),代表這組測資有幾個數字,

第二行有N個正整數為h1,h2,h3,...,hN,每個數字皆不超過10000

Output Format

對於第i個數字,如果它和第j個數字交換可以使爛度最小則輸出j,如果有多個j可以讓爛度最小,輸出最小的j。

格式詳見範例。

Sample Input

2
5
2 3 4 5 7
5
7 2 3 1 5

Sample Output

1 2 3 4 5
4 5 2 1 2

Hints

Problem Source

原TIOJ1329 / TFcis10 留社考。Problem Setter:seanwu

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1