k800. 解題愛老鼠（太空人老鼠） - 高中生程式解題系統

內容

老鼠是個天才兒童，一歲就會寫程式，五歲時在 ZJ 看到解出 300% 的題目就可以去太空公司面試。

在老鼠的努力下，他成功得到面試的機會，因為老鼠既強壯又聰明，成功當上了太空人，他也成為了地球上第一個太空人老鼠。

老鼠的任務是維護衛星，有 $n$ 個衛星，第 $i$ 個衛星離地表的高度是 $a_{i}$ 公尺（ $1 \leq i \leq n$ ）。

如果衛星的高度過低，就會發出警報，所以老鼠想要讓每個衛星的高度都不低於 $C$ 公尺。

老鼠可以花費 $c_{i, j}$ 單位的成本用重力波的技術，將第 $i$ 個衛星的高度 $- 1$ 公尺，並讓第 $j$ 個衛星的高度 $+ 1$ 公尺，也就是讓 $a_{i} - 1$ 、 $a_{j} + 1$ ，且過程中不能出現某個衛星高度小於 $0$ 的情況。

請問最少要花費多少成本才能使每個衛星高度至少是 $C$ 公尺呢？

輸入說明

第一行輸入 $n, C$ ，代表有幾個衛星和每個衛星高度至少要幾公尺。

第二行輸入 $a_{1} \sim a_{n}$ ，代表每個衛星初始的高度。

接下來 $n$ 行，第 $i$ 行輸入 $n$ 個整數 $c_{i, 1} \sim c_{i, n}$ 。

$1 \leq n \leq 300$
$0 \leq C \leq 10^{9}$
$0 \leq a_{i} \leq 10^{9}$
$0 \leq c_{i, j} \leq 10^{6}$
保證 $\sum_{i = 1}^{n} a_{i} \geq n \times C$ ，也就是一定存在使每個衛星高度至少有 $C$ 公尺的方法。

輸出說明

輸出一個整數代表最少要花多少成本才能使每個衛星高度至少有 $C$ 公尺。

範例輸入 #1

1 100
48763
99999

範例輸出 #1

範例輸入 #2

3 23
11 45 14
0 1000 2
1 123 1000
1000 1000 1000

範例輸出 #2

測資資訊：

記憶體限制： 128 MB
不公開測資點#0 (10%): 1.5s , <1K
不公開測資點#1 (10%): 1.5s , <1K
不公開測資點#2 (10%): 1.5s , <1M
不公開測資點#3 (10%): 1.5s , <1M
不公開測資點#4 (10%): 1.5s , <1M
不公開測資點#5 (10%): 1.5s , <1M
不公開測資點#6 (10%): 1.5s , <1M
不公開測資點#7 (10%): 1.5s , <1M
不公開測資點#8 (10%): 1.5s , <1M
不公開測資點#9 (10%): 1.5s , <1M

提示：

正當老鼠在維護衛星的時候，看到不遠處有一個人漂過來

老鼠：「豬大哥，你怎麼在這裡？！」

豬大哥：「我又活回來了。」

（未完待續）

-----------------------------------------------------------------------------

在範例一中，因為一開始已經滿足條件了，不需要任何操作，花費為 $0$ 。

在範例二中，可以進行 $21$ 次花費 $c_{2, 1} = 1$ ，使 $a_{2} - 1, a_{1} + 1$ 的操作，此時 $a = [32, 24, 14]$ ；再進行 $9$ 次花費 $c_{1, 3} = 2$ ，使 $a_{1} - 1, a_{3} + 1$ 的操作，最終 $a = [23, 24, 23]$ ，共花費 $21 \times 1 + 9 \times 2 = 39$ 。

-----------------------------------------------------------------------------

$100 % ：無特別限制$

標籤:

出處:

第七屆簡單的小競賽 [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
39292	becaido (Caido)	k800		225	2024-02-02 16:52