切換
舊版
前往
大廳
主題

ZeroJudge - f313: 2. 人口遷移 解題心得

Not In My Back Yard | 2020-10-20 17:36:53 | 巴幣 2 | 人氣 730

題目連結:


題目大意:
輸入第一列給定四正整數 R 、 C 、 m 、 k (1 ≦ R 、 C 、 m ≦ 50 , 4 ≦ k ≦ 50),代表有一個 R 列 C 行的城市網格,而現在要模擬 m 天後的人口分布。

接著有 R 列的輸入,每列給定 C 個整數,代表著城市網格每格在第 0 天時的人數。當有一格的人數為 -1 時,則代表著該格並非城市,人口移動時會忽略此格。

每一天,對於每個城市,其會向每個相鄰(上下左右)的城市遷移 (前一天城市人數 ÷ k) 個人(無條件捨去,即取商數)。

求第 m 天時,所有城市中人數最少以及最多之值為何?



範例輸入:
2 3 4 1
10 2 -1
5 -1 2


範例輸出:
2
7


解題思維:
除了儲存城市網格人數的二維陣列以外,需要另一個二維陣列作為「暫存」,所有人口的更動應先存在該陣列中,所有城市做完之後才將該陣列的內容套用到城市網格。

每一次就是掃過陣列的每一格,對於每格不是 -1 之值的,掃過其相鄰城市。並對於每個相鄰城市不是 -1 的,送出 (人數 ÷ k) 個人。注意,這個更動的資訊應先存在暫存陣列裡,否則直接覆寫城市陣列會導致其他城市計算錯誤。

而上述過程要做 m 次。做完之後掃過城市網格陣列,求其中的最小值以及最大值(請記得忽略 -1 的格子),即得到所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作