[TIOJ] 1860. Ch1-8.白之夢

題目連結:http://tioj.infor.org/problems/1860
本題並不是甚麼演算法題,而是一種奇特(?的機率模型,有人稱作秘書問題,其詳細的證明可見維基百科,這邊只講做法,就是若總共有n隻小蘿莉是你要比對的,則把前$\frac{n}{e}$當作基準來比會有最好的結果,所以當我們就在前$\frac{n}{e}$個中找出最大值,接下來若遇到比他大的就選,如果都沒有就選最後一個,大概就這樣吧
#include "lib1860.h"
#include <math.h>
int main(){
        int n = Start_The_Loli_Dream();
        while(n--){
                int m = Count_How_Many_Loli(),max=-2147483648;
                int size = (int)round(m*(double)0.367879441171442);
                int a = m-size;
                while(size--){
                        int l = Get_Loli_Moeness();
                        if(l>max)
                                max=l;
                }
                bool choosed=false;
                while(a--){
                        int l = Get_Loli_Moeness();
                        if(l>max){
                                You_Choose_This_Loli();
                                choosed=true;
                                break;
                        }
                }
                if(!choosed)You_Choose_This_Loli();
        }
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology