PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] NPSC2007交換禮物、2005誰先晚餐的證明

看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間16年前 (2008/11/25 10:14)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

※ 引述《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