e356：愛的法則，即是犧牲的法則

e356：愛的法則，即是犧牲的法則

題目連結：e356：愛的法則，即是犧牲的法則

題意：

總共有n個人，每個人都有一個評價分數，但是只有在你見過他/她時才會知道分數如何。

你可以選擇跟他/她結婚或是拒絕，且你做的決定是不可逆的。

你可以假設評價分數不會重複。

請問你要怎麼讓你"結到最好評價的人"的機率最大化呢?

以下提供一個策略:

選定一個犧牲樣本區間[1,r]，設犧牲樣本中最好的評價為C，再從[r+1,n]中選第一個評價大於C的人。(如果都沒有則都不選，一輩子單身。

然而機率總隨著r的更動而有變化。

現在把n固定為9230000，請輸出正確的r讓你找到真愛的機率最大化!

評測會先產生一不重複隨機數列(每次送出都不一樣)，然後按照上面的策略選一個數，如果選中的是最大的數則AC，否則WA。

解法：

標準的秘書問題

最好的 r 為 9230000/e≒3395527

time:2.2s

memory used:70.8MB

code:

1. #include<iostream>
2. #define e 2.718281828
3. using namespace std;
4. int main(){
5.     cout<<(int)(9230000/e)<<'\n';
6. }

本人的分享到此結束

若有更好的想法或建議,請在留言區留言喔