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