主題

ZeroJudge - f818: 物競天擇 (Survival) 解題心得

Not In My Back Yard | 2021-05-09 00:00:14 | 巴幣 0 | 人氣 63

題目連結:


題目大意:
輸入第一列給定一正整數 N (2 ≦ N ≦ 2000),代表有 N 隻小獅子。接著的一列給定 N 個正整數 H (1 ≦ H ≦ 1000),代表每隻小獅子的身高;最後一列給定 N 個正整數 W (1 ≦ W ≦ 1000),代表每隻小獅子的體重。

請找到身高 × 體重之值最小的小獅子(保證只會有一隻為最小),並輸出牠的身高以及體重。



範例輸入:
範例輸入 #1
2
145 34
21 55

範例輸入 #2
4
361 619 555 855
419 758 549 240

範例輸入 #3
5
17 100 40 111 68
157 151 25 173 197


範例輸出:
範例輸出 #1
34 55

範例輸出 #2
361 419

範例輸出 #3
40 25


解題思維:
就是一題單純的找最大值之問題。

假設 H[i] 、 W[i] 代表著第 i 隻獅子的身高以及體重。則令 Mh 、 Mw (初始值皆設為很大的數字(如 1001 以上),代表任一獅子之乘積都會比該值小)代表著當前乘積最小的獅子之身高、體重。

接著就是掃過所有獅子的身高體重,然後對於每個 H[i] 、 W[i] 判斷 H[i] × W[i] 是否 < Mh × Mw。如果符合則更新 Mh 、 Mw,使得 Mh = H[i] 、 Mw = W[i]。

掃完之後,Mh 以及 Mw 之值即為所求。




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

創作回應

更多創作