切換
舊版
前往
大廳
主題

ZeroJudge - e356: 愛的法則,即是犧牲的法則 解題心得

Not In My Back Yard | 2019-09-12 22:30:32 | 巴幣 0 | 人氣 120

題目連結:


題目大意:
本題即是一個典型的「秘書問題」。每個人都有一個分數,「看過」一個人之後換到下一個就不能回來選擇此人。要試著讓選到分數最大的人之機率最大化。

有一個選擇的策略是:
忽略前 r 個人(假設總共有 n 個人),並假設前 r 個人裡面分數最大的為 C 。接著依序看剩下的 n - r 個人,一看到有比 C 大的分數,就選擇該人;如果都沒出現比 C 大的,就不會選到任何人。

本題會隨機生成 n = 9230000 個整數,並根據解題者輸出的 r 值去執行以上的策略。



範例輸入:
(無輸入)


範例輸出:
(輸出一個能使選到最大的數字之機率最大化的 r 值)


解題思維:
雖然可以找到一個數字 r ≒ 3395527,可以使此策略挑到最大數的機率為最大。但是,實際上還是需要靠一些運氣,畢竟大約只有 36.787 % 的機率會成功挑中。

而這個神祕的數字 r 來自於 (n = 9230000) ÷ e 。詳情可以去維基頁面看相關的公式推導。



(說真的,這題沒有必要放程式碼。真的只是輸出一個數字而已)
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作