網頁

2014年1月21日 星期二

UVa 11413 Fill the Containers

題意:   
  給定N個牛奶瓶子,以及M個容器,每個牛奶瓶子n[i]的容積不一樣(題目會給),我們所要求的是一個"容器"的容積至少要"多少'才能使得只用'M'個就能把那N個牛奶瓶裝完,而裝的時候有幾個規則:第一個牛奶瓶倒入容器後才能換第二個,每個牛奶瓶只能到入同個容器(因此如果該容器還有空間但不夠裝完這個牛奶瓶的話,就只能換下個容器)。
  從Example來看:5個牛奶瓶子要到入"3"個容器裡(沒錯,題目規定不多不少就是3個),那麼至少每個容器的容積要6才能滿足該條件{(1,2,3),(4),(5)}。 

想法:   
  使用binary search找出符合的條件,Left=(所有牛奶瓶容積最大的那個),Right=(所有牛奶瓶的容積)。