網頁

2013年12月29日 星期日

UVa 10026 Shoemaker's Problem

  本題是指鞋匠一次只能選一個工作做,以Sample Input為例,如果先選第一件工作,它需要完成的時間為3天,那麼這3天就無法做其他工作,罰金就為3*(1000+2+5)元,本題要找出選擇工作的次序使得罰金最小。

想法:
  兩相鄰事件a(Ta,Fa),b(Tb,Bb)無論排成ab或是ba,其他部分的罰金是固定的所以差異在於ab(Ta*Fb)還是ba(Tb*Fa)的損失較小

假如是ab較小,則
  • (Ta*Fb)<(Tb*Fa) 
  • => (Fa/Ta)>(Fb/Tb) 
a的(罰金/時間)比較大

因此本題解法是將每個工作(Fi/Ti)由大到小排序