看板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