※ 引述《Iriss (好害羞的愛情故事)》之銘言： : ※ 引述《sophialiege ()》之銘言： : : 只有一個水龍頭很容易, 如果有兩個水龍頭可以排成兩隊呢? : : 解: : : 先排一隊 (sort ni in non-decreasing order) : : 哪一水龍頭空了就讓最前面一個上 : : n個水龍頭也適用 : 既然我回了是 NP-hard，那只好來想一個反例 : 假設五個人 : 先排序 10, 9, 5, 4, 3 : Greedy algorithm will give : 1. 10 4 : 2. 9 5 3 total = 17 : But optimal schedule is : 1. 10 5 : 2. 9 4 3 total = 16 我發現我看錯了，這題問的是等待時間和... 不過我舉的例子依然可以用 Greedy algorithm gives waiting time 0 + 0 + 9 + 10 + 14 = 33 Optimal waiting time is 0 + 0 +10 + 9 + 13 = 32 不過是不是 NP-hard 還要再想想。 -- 迴旋如藤－ 蔓 波動的溫柔拂飛柳絮 淡妝 散、漫、在西施採菱的湖邊 --

※ 發信站: 批踢踢兔(ptt2.cc) ◆ From: 68.181.255.120