[程式] 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 的複雜度)：

	/*
	* =====================================================================================
	*
	* Filename: 166C.cpp
	*
	* Description: codeforces 166C: Median
	*
	* Version: 1.0
	* Created: 2018/03/19 (yyyy/mm/dd)
	* Revision: none
	* Compiler: g++
	*
	* Author: lionking
	* Organization: None
	*
	* =====================================================================================
	*/
	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int main()
	{
	constexpr int MAXN = 501;
	int n, x;
	int num[MAXN] = {0};
	while (scanf("%d %d", &n, &x) == 2) {
	for (int i = 0; i < n; ++i) { scanf("%d", num + i); }
	int ans = 0;
	if (any_of(num, num + n, [&x](const int v) -> bool { return (v == x); }) == false) {
	// if the target number is not in the given array, then add it to the array
	num[n++] = x;
	++ans;
	}
	sort(num, num+n);
	int low = lower_bound(num, num+n, x) - num; // the first existence of x
	int high = upper_bound(num, num+n, x) - num; // the last existence of x
	int median = (n - 1) >> 1; // median
	if (median < low) { ans += low * 2 - n + 1; }
	else if (median >= high) { ans += n - high * 2; }
	printf("%d\n", ans);
	}
	return 0;
	}

view raw codeforces-166C.cpp hosted with ❤ by GitHub