[問題] NPSC2007交換禮物、2005誰先晚餐的證明
看板Prob_Solve (計算數學 Problem Solving)作者oliver111 (冷雨)時間16年前 (2008/11/20 22:55)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/2 (看更多)
http://0rz.tw/6f594
http://0rz.tw/a555N
這兩題我直覺知道怎麼解，但是不知道為什麼...
我的作法是：
交換禮物-用模擬法，先排序，然後最多禮物的人和第二多、第三多的依序交換，每次交換
完重新排序。最後如果禮物有剩則失敗。
但是怎麼證明如果這個方法禮物有剩，則禮物用其他方法也不可能交換完畢？
誰先晚餐-用貪心法，使吃餐點所需時間最久的人先吃。
但是怎麼證明這樣就是最好的方法？
請程式（或者數學）高手不吝指教...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.117.20.1
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
