Codeforces #23 C Oranges and Apples

題意﹕給了$2N-1$個箱子，每個箱子分別載有 $A_i$ 和 $O_i$ 個蘋果和橙。要求選出 $N$ 個箱子使得蘋果和橙的總數至少為總數的一半。 $A_i, O_i \ge 0$ 。

設蘋果和橙的總數為 $A$ 和 $O$。換句話說，就是求一集合 $\mathcal{I}\subseteq \{1\cdots 2N-1\},\, |\mathcal{I}| = N$ 使得

$$\sum_{i\in\mathcal{I}}A_i \ge \frac{A}{2},\quad \sum_{i\in\mathcal{I}}O_i \ge \frac{O}{2}$$

我的做法比較不確定，就是任意隨機取一排列 $\sigma$ 使得首 $N$ 個箱子符合條件。

正確的做法應該是這樣。不失一般性下假設

$A_1 \le A_2 \cdots \le A_{2N-1}$

把奇數項設為 $Q$ ，偶數項設為 $P$ ，則有

$Q_1 \le P_1 \le Q_2 \le P_2 \cdots P_{N-1} \le Q_N$

定理 1﹕ $\sum_i Q_i \ge \frac{A}{2}, \sum_i P_i + Q_N \ge \frac{A}{2}$ 。

對於 $1 \le i \le N-1$ , 皆有 $Q_{i+1} - P_i \ge 0$ 。因此 $Q_1+\sum_{i=1}^{N-1}Q_{i+1}-P_i \ge 0$ ，故 $\sum_i Q_i$ 至少為 $A$ 的一半。

另外，對於 $1 \le i \le N-1$ 則有 $P_i-Q_i \ge 0$ 。因此 $Q_N+\sum_{i=1}^{N-1}P_i-Q_i \ge 0$ ，故 $Q_N + \sum_i P_i$ 至少為 $A$ 的一半。

因此，把箱子依數量排序則有兩種取法使得其蘋果數的總和至少為 $A$ 的一半，而且它們皆取了第 $2N-1$ 個箱子。那麼這兩種取法的橙的數量分別有 $X = \sum_{i=1}^{N} O_{2i-1}$ 和 $Y = \sum_{i=1}^{N-1} O_{2i}+O_{2N-1}$ 。

設 $Z = Y - O_{2N-1}$ 。因為 $X + Z = O$ 。若 $X < \frac{O}{2}$ 則有 $Z \ge \frac{O}{2}$ ，反之亦然。而 $Y \ge Z$ ，因此在結論中可把 $Z$ 替換成 $Y$ 。因此按這個方法去選取箱子則保証答案永遠存在。