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