前往
大廳
主題

ZeroJudge - e901: 婚姻介紹所 解題心得

Not In My Back Yard | 2020-10-23 19:39:53 | 巴幣 0 | 人氣 215

題目連結:


題目大意:
輸入有多筆測試資料(≦ 10 筆)。每筆測資第一列給定一正整數 N (N ≦ 100000,當 N = 0 時代表輸入結束),代表有 N 位男生以及 N 位女生。

接著一列給定 N 個正整數,代表每位男生的「積分」;再接著一列同樣也給定 N 個正整數,代表每位女生的「積分」。其中積分之值介於 1(含) ~ 9(含)之間。

當有一對男女之積分和 > 10 時,即可以形成一個「配對」,且每形成一個配對可以獲得 200 金幣之傭金。試問,最多可以形成幾個「配對」並獲得多少的傭金?



範例輸入:
5
9 1 8 8 6
5 9 8 2 4
10
5 9 9 8 5 2 5 2 5 2
9 9 4 4 9 3 2 9 5 7
0


範例輸出:
4 800
8 1600


解題思維:
由小到大窮舉所有可能的分數總和 11 、 12 、 …… 、 18 ,並對於每個分數去看看有哪些男女可以配對(前面先統計男女各自有幾個 9 分、 8 分等等)。

例如對於分數和 = 11 的,其有以下可能:
9 分男 + 2 分女
8 分男 + 3 分女
7 分男 + 4 分女
6 分男 + 5 分女
5 分男 + 6 分女
4 分男 + 7 分女
3 分男 + 8 分女
2 分男 + 9 分女
然後對於每個可能(例如 9 分男配 2 分女),看男女哪個數量比較少。

例如 9 分的男性比較少,因此就只能形成那麼多對(不可能超過,因為人數有限);配完之後就將 9 分男、 2 分女的數量都減去剛剛成功配對的數目,然後繼續窮舉之過程。

把所有窮舉之分數和下面的所有可能之成功配對數目全數加起來,即是所求的最大配對數,該數乘以 200 後即是所求的最大傭金。




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

創作回應

更多創作