IOI 2002 Utopia Divided

諗左好耐, 最後都係去左搵果年既 report

的確是很巧妙的做法..! 不過唔易諗到



定義 alternating sequence為一數列 X1, X2, X3, ... Xn
其中 |X1| < |X2| < |X3| < ... < |Xn|
而且 sign 是互相交替的

例如 -1,4,-6,7
和 2,-3,7,-10




alternating sequence 有一個性質
就是 整條數列之和的正負 等同於 Xn 的正負

例如Sum (-1,4,-6,7) = 4  [與7同號]
Sum (2,-3,7,-11) = -5  [與-11同號]



1D 的情況
要將 n 個數字 X1, X2 ... Xn 排好和 assign 正負值, 而且頭 x 個之和是指定為正或負 ( S[x] = '+' OR S[x] = '-' )




先將果 N 個數字由小至大 sort
然後 assign 正負相間, 做成一條 alternating sequence

咁一開始取值正定負呢?


由 alternating sequence 的特性, 為了滿足 S[n] , 因此 Xn 應與 S[n] 同號

這樣便可確保 Sum( X1,X2,X3...Xn) 的正負號必滿足 S[n]
而且入面數字的次序點調都得


咁點先可以滿足 S[n-1] 呢?
由該性質可得, 如果可以整到一條 長度n-1, 最尾那個數字的正負號=S[n-1] 的話, 便能滿足 S[n-1]


現在是 X1, X2, X3, X4, ...Xn
有兩個選擇,

1)
X1, X2, X3... Xn-1

2)
X2, X3, X4... Xn


用邊個選擇? 就係睇 S[n-1] 同 Xn 同號 還是 同 Xn-1 同號 !!

由於是一條 alternating sequence, Xn 必與 Xn-1 不同號, 因此總能找到與 S[n-1] 同號的

By induction, 重覆此步驟 n-1 次, 便能滿足 S[1]..S[n] !


例子:
n = 5
S[ ] = {-,-,-,+,+}
X[ ] = {2,3,4,5,6}


Step 1 [ assign 正負, 使 X5 與 S[5] 同號 ]

X[ ] = {+2,-3,+4,-5,+6}


Step 2 [滿足 S[4] ]
X[ ] = {-3,+4,-5,+6,+2}

Step 3 [滿足 S[3] ]
X[ ] = {-3,+4,-5,+6,+2}

Step 4 [滿足 S[2] ]
X[ ] = {+4,-5,-3,+6,+2}

Step 5 [滿足 S[1] ]
X[ ] = {-5,+4,-3,+6,+2}