作者Leon (Achilles)
站内Prob_Solve
标题Re: [问题] NPSC2007交换礼物、2005谁先晚餐的证明
时间Tue Nov 25 10:14:47 2008
※ 引述《oliver111 (冷雨)》之铭言：
: http://0rz.tw/6f594
: http://0rz.tw/a555N
: 这两题我直觉知道怎麽解，但是不知道为什麽...
: 我的作法是：
: 交换礼物-用模拟法，先排序，然後最多礼物的人和第二多、第三多的依序交换，每次交换
: 完重新排序。最後如果礼物有剩则失败。
: 但是怎麽证明如果这个方法礼物有剩，则礼物用其他方法也不可能交换完毕？
: 谁先晚餐-用贪心法，使吃餐点所需时间最久的人先吃。
: 但是怎麽证明这样就是最好的方法？
: 请程式（或者数学）高手不吝指教...
我看了第二题, 这可以这样解.
Shortest time will be maximum of sum(Cj) + Ej, 1 <= j <= N.
用中文说, 大家全部吃完的时间, 是 Maximun of 每个人吃完的时间.
Assume E (k+1) > E(k)
then, if we switch k and k+1 term...
compare , max { sum C(1_k-1) + C(k+1) + E(k+1), sum C(1_k+1) + E(k) } with
max{ sum C(1_k) + E(k), sum C(1_k+1) + E(k+1) }
obvious, after switch it's strickly smaller....
--
赵客缦胡缨，吾钩霜雪明。银鞍照白马，飒沓如流星。
十步杀一人，千里不留行。是了拂衣去，深藏身与名。
闲过信陵饮，脱剑膝前横。将炙啖朱亥，持觞劝侯赢。
三杯吐然诺，五岳倒为轻。眼花耳热後，意气素霓生。
就赵挥金锤，邯郸先震惊。千秋二壮士，烜赫大梁城。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 128.125.20.198