大意是給了n個實數，代表了n個人需要完成身體檢的時間。有m個醫生為他們作身體檢查。一個人可以分開不同時段給不同醫生作身體檢查，唯獨是一個人不可以同一時間給多於一個醫生作身體檢查。另，醫院時刻也只能有這兩個情況﹕要麼m個醫生都在為不同的人作身體檢查，要麼就只有一個人在加班。問，最少需要多久能為所有人完成檢查？
首先，可以通過安排，使得工模式為「m位醫生工作 --> 一醫生工作」。如果一個人不可以分開時段給不同醫生檢查，可以得出問題的一種特例就是partition問題，是NP-Complete的。正因為可以任意分開時段，我們第一個想法就是直接取平均數。不過需要注意另一個限制「一個人不可以同一時間給多於一個醫生作身體檢查」。因為像5和5.1而m=2的話，雖然平均數是5.05，但是第二個人的0.1無法分拆成兩個不同時段。可以直接觀察得出，假若有一個需時大於平均數的話，剩出來的時間基本上無法放到任何平均數線之前，因為這位人本身已經獨佔了平均數線以前的時段。若然沒有這樣的問題的話，那麼我們必定可以安排所有人在平數時限前完成檢查。基於平均數本是最優的，所以我conjecture了這個算法﹕
為所有數取平均數，然後檢查每個數，若大於平均數，把多出的加到答案裡，然後把它們設為平均數，完成後重新再取平均數檢查；否則把平均數加到答案裡，並輸出答案。
一次AC。
沒有留言:
張貼留言