[程式] codeforces 166C: Median

[題意] 給兩個正整數 n (n <= 500) 跟 x (x <= 100,000)，並且再給你一串含有 n 個數字的陣列 A，問如果要讓 A 經過排序後的中位數是 x 的話最少要往 A 裡面加入幾個數字？

舉個例子來說：假設 n = 3, x = 10, A = {10, 20, 30}。此時最少要往 A 中加入 1 個 <= 10 的數字才能讓 A 經過排列後的中位數是 10。

另一個例子是 n= 3, x = 4, A = {1, 2, 3}。此時最少要加入 4 個 >= 4 的數字才能讓 A 經過排序後其中位數是 4。

[解法]
首先我們從上面兩個例子可以發現，不論是甚麼情況，加入的數字只要等於 x 就好，不需要考慮其他數字，因此剩下來的問題就是到底要加入多少 x？

因為題目問的是 A 經過排序後的中位數，當然，我們先把 A 排序一次後再來計算會方便很多，這邊就可以簡單地歸納出三種情形：

1. x 已經落在 A 的中位數了：這種情況下當然什麼都不用做
2. x 出現在 A 中的區間 [a, b] 比目前 A 的中位數還前面 (a, b 都是 index)
3. x 出現在 A 中的區間 [a, b] 比目前 A 的中位數還後面

先看第 2 點：這種情況表示我們丟進去 A 中的 x 的數量必須要能夠讓 b 這個位置變成新的中位數的位置。(程式中的第 46 行)

相對的，第 3 點的情況則是我們丟進 A 中的 x 的數量必須要能夠讓 a 這個位置變成新的中位數的位置。(程式中的第 45 行)

搞清楚這兩個條件後，簡單的算一下就能知道最少要丟多少數量進去 A 中囉。

值得注意的一個小細節是：A 中到底有沒有 x 呢？因為如果 A 中如果沒有 x，此時不論如何都必須要先加入至少一個 x 到 A 中。但要解決這個問題也不難，反正我只要先把 A 掃一遍，沒發現 x 就先把 x 丟進去 A 中再處理就好。

實作結果如下 (整體的時間複雜度就等同 sort 的複雜度)：