看板ACMCLUB
标 题Re: [闲聊] 水龙头
发信站批踢踢兔 (Tue Mar 28 15:47:01 2006)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
※ 引述《pangfeng (P老师)》之铭言：
: 有n个人排队取水, 第i个人取水需ti.
: 问如何排队取水, 使所有人的等待时间和为最小?
:
: --
: 只有一个水龙头很容易, 如果有两个水龙头可以排成两队呢?
:
It's NP hard.
The proof is here:
http://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec03.pdf
(这是我上学期的期末考题)
--
回旋如藤－
蔓 波动的温柔拂飞柳絮
淡妆
散、漫、在西施采菱的湖边
--
※ 发信站: 批踢踢兔(ptt2.cc)
◆ From: 68.181.255.120