: → cklin:Which makes me wonder if May's solution is correct :) 推 03/23 12:04
I admit my original note is not right: it should be
Insert the new task in the middle is not better than put it in the back.
(not in the front as I originally stated)
The proof is intuitive. Insert in the middle won't help reduce t, and
the only case that it doesn't create any further delay has to satisfy
two requriements:
1. Its binding job is put in the end.
2. Its printing job is done without affecting the binding jobs of
the books behind it.
Otherwise, t is increased by at least p(k) - T(k-1)
The second requirements is stronger than p(k) \leq T(k-1) in the put in
the back case. And if the requiremnet is not met, insert in the middle
didn't give a better answer either.
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 68.181.253.45
討論串 (同標題文章)