網頁

2014年4月16日 星期三

UVa 11389 The Bus Driver Problem

題意:
    有n個司機,早班有n條路線,晚班也有n條路線,這2n條路線都有不同的距離,要安排每一個司機早班和晚班各一條路線,但是如果早班+晚班的路線距離超過d的話,超過每1單位就要加班費r元,求如何安排路線給每位司機使得全部加班費為最小,並輸出。

想法:
    將早班n條路線由小到大排序,晚班也是,為了使得加班費總和最少,安排時就要盡量填滿d,因此早班最短配上晚班最長路線,然後早班第二短配上晚班第二長,.....依此類推。如果最短配上最短,會導致該路線和遠小於d,表示浪費了這位司機還剩下的距離,因此要盡量讓每位司機平均填滿d。