[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();
        }
}