看板ACMCLUB
标 题Re: [闲聊] 水龙头
发信站批踢踢兔 (Tue Mar 28 16:16:42 2006)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
※ 引述《sophialiege ()》之铭言：
: ※ 引述《pangfeng (P老师)》之铭言：
: 只有一个水龙头很容易, 如果有两个水龙头可以排成两队呢?
: 解:
: 先排一队 (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
--
回旋如藤－
蔓 波动的温柔拂飞柳絮
淡妆
散、漫、在西施采菱的湖边
--
※ 发信站: 批踢踢兔(ptt2.cc)
◆ From: 68.181.255.120