TopCoder

8e7
$\huge X語言專家 $(TIOJ 1269)

User's AC Ratio

96.7% (29/30)

Submission's AC Ratio

60.2% (62/103)

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 1

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

Sample Output 1

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 (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1