Re: [請益] 學測分發規則
剛剛看到這個問題覺得很有趣，在臉書上發動態和朋友們聊了一下，整理之後放上來。
這個問題叫做「穩定婚姻問題」，英文叫做Stable Marriage Problem。
中文維基：http://tinyurl.com/bnpvrh9
英文維基：http://tinyurl.com/ccs6nak
並且，在英文維基當中有提到其中一種情況會使分發結果超過一組解。
另外，我的朋友給了一個連結：
http://ip194097.ntcu.edu.tw/iug/ungian/chokphin/Hoagu/hunhoat/hunhoat.htm
是一篇十幾年前關於考試分發入學演算法的論文，大家可以參考一下。
接下來大致上描述一下演算法的跑法：
1. 假設所有人的第一志願錄取。
2. 將所有超額的校系放入佇列。
3. 每次取出佇列裡的元素，將超額的校系最低分者取出，將其志願退後，並且如果他的
新志願超額，則將新志願放入佇列中。
對於各校系的最低分我們可以用Heap去做維護。
假設一個人最多可以填N個志願、共M個考生、每個校系的正備取人數和是K，我們可以得
到這個演算法的時間複雜度是O(NMlogK)，其中logK是以2為底的對數。
以102年的狀況來說，N=6，M估計為150000(應該會比較小)，K假設200好了，計算出來的
結果應該可以在1秒之內就跑出來，比論文中的13秒快上許多(科技在進步)。
至於非唯一解的情況，好像是要以分發委員會的程式為主，我不知道正備取的假設會不會
使穩定婚姻問題變成唯一解。
※ 引述《skgg (陳帥)》之銘言：
: 問題是：正取的科系如果志願序排很後面是否仍保證會上
: 如果是的話感覺很容易互卡產生矛盾啊...
: 有請確定的人回答一下<(_ _)>
如果依照這種思維的話，不可能出現前面備取沒上，後面正取也沒上的情況。
可以這樣思考：
1.假設現在前面備取都沒有上，考慮正取
2.正取校系超額，丟進佇列
3.佇列非空，取出佇列內元素
4.考慮該校系剔除最低分者(這裡的最低分者一定不可能是正取者)
5.更新為正取
這樣就可以避免掉skgg問的這個問題了
如果有敘述不清或是錯誤的地方還請板上大大幫忙修正。
小弟今年順利錄取台大資管了，祝全國考生同胞大學考試順利！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.167.44.9
推
04/20 19:35, , 1F
04/20 19:35, 1F
推
04/20 22:31, , 2F
04/20 22:31, 2F
推
04/20 22:34, , 3F
04/20 22:34, 3F
推
04/20 23:16, , 4F
04/20 23:16, 4F
推
04/21 00:44, , 5F
04/21 00:44, 5F
→
04/21 00:45, , 6F
04/21 00:45, 6F
→
04/21 03:11, , 7F
04/21 03:11, 7F
推
04/21 08:10, , 8F
04/21 08:10, 8F
→
04/21 08:13, , 9F
04/21 08:13, 9F
推
04/21 09:08, , 10F
04/21 09:08, 10F
推
04/21 14:23, , 11F
04/21 14:23, 11F
推
04/22 19:41, , 12F
04/22 19:41, 12F
推
04/25 23:33, , 13F
04/25 23:33, 13F
→
09/11 13:51, , 14F
09/11 13:51, 14F
討論串 (同標題文章)