作者oliver111 (冷雨)
看板Prob_Solve
标题[问题] NPSC2007交换礼物、2005谁先晚餐的证明
时间Thu Nov 20 22:54:59 2008
http://0rz.tw/6f594
http://0rz.tw/a555N
这两题我直觉知道怎麽解，但是不知道为什麽...
我的作法是：
交换礼物-用模拟法，先排序，然後最多礼物的人和第二多、第三多的依序交换，每次交换
完重新排序。最後如果礼物有剩则失败。
但是怎麽证明如果这个方法礼物有剩，则礼物用其他方法也不可能交换完毕？
谁先晚餐-用贪心法，使吃餐点所需时间最久的人先吃。
但是怎麽证明这样就是最好的方法？
请程式（或者数学）高手不吝指教...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.117.20.1