這題相當於：給定一個 $\color{black}{n\times m}$ 的矩陣 $\color{black}{\{a_{i, j}\}}$，其中 $\color{black}{a_{i, j}\ge0}$，請找出某個 $\color{black}{i^*}$ 與 $\color{black}{j^*}$ 以最小化
\[\color{black}{S(i^*, j^*) := \sum_{i=1}^n\sum_{j=1}^m(|i^*-i|+|j^*-j|)a_{i, j}.}\]
注意我們有
\[\color{black}{ \begin{split} S(i^*, j^*) &= \sum_{i=1}^n\sum_{j=1}^m|i^*-i|a_{i, j} + \sum_{i=1}^n\sum_{j=1}^m|j^*-j|a_{i, j}\\ &= \sum_{i=1}^n\left(|i^*-i|\sum_{j=1}^ma_{i, j}\right) + \sum_{j=1}^m\left(|j^*-j|\sum_{i=1}^na_{i, j}\right) \end{split} }\]
令第 $\color{black}{i}$ 列的和 $\sum_{j=1}^ma_{i, j}$ 為 $\color{black}{S^r_i}$，第 $\color{black}{j}$ 行的和 $\color{black}{\sum_{i=1}^na_{i, j}}$ 為 $\color{black}{S^c_j}$，則上式可進一步化簡成
\[ \color{black}{ S(i^*, j^*) = \sum_{i=1}^nS^r_i|i^*-i| + \sum_{j=1}^mS^c_j|j^*-j|. } \]
如果我們可以解決問題 A：
|
問題 A：給定一非負實數數列 $\color{black}{c_1, c_2, \ldots, c_n}$，請找出某個正整數 $\color{black}{i^*}$ 以最小化 $S(i) := \color{black}{\sum_{i=1}^nc_i|i^*-i|}$。 |
就能解決原本的問題。注意問題 A 有個顯然的 $\color{black}{\Theta(n^2)}$ 時間的演算法，而由於本題已存在輸入的 $\color{black}{\Theta(nm)}$ 門檻，採用此演算法已可通過本題。
以下介紹如何在 $\color{black}{O(n)}$ 時間內算出問題 A 的答案。設 $\color{black}{k \in \{1, 2, \ldots, n-1\}}$，注意我們有
\[\color{black}{\begin{split} S(k+1)-S(k) &= \sum_{i=1}^n c_i|k+1-i| - \sum_{i=1}^nc_i|k-i|\\ &= \sum_{i=1}^nc_i(|k+1-i|-|k-i|)\\ &= \sum_{i=1}^kc_i((k+1-i)-(k-i)) + \sum_{i=k+1}^nc_i((i-k-1)-(i-k))\\ &= \sum_{i=1}^kc_i - \sum_{i=k+1}^nc_i. \end{split}}\]
由 $\color{black}{\sum_{i=1}^kc_i}$ 隨著 $\color{black}{k}$ 遞增，$\color{black}{\sum_{i=k+1}^nc_i}$ 隨著 $\color{black}{k}$ 遞減，我們知道 $\color{black}{S(k+1)-S(k)}$ 隨著 $\color{black}{k}$ 遞增，因此 $\color{black}{i^*}$ 為滿足 $\color{black}{\sum_{i=1}^kc_i\ge\sum_{i=k+1}^nc_i}$（即 $\color{black}{2\sum_{i=1}^kc_i}\ge\sum_{i=1}^nc_i$）的最小整數 $\color{black}{k}$，可在 $\color{black}{O(n)}$ 時間內求出。