11413 : Fill the Containers ★★★★☆ 題組：Problem Set Archive with Online Judge 題號：11413 : Fill the Containers 解題者：詹鈞皓、丘珮珊 解題日期：2015年6月11日 題意：一個輸送帶上有N(1<=N<=1000)瓶牛奶，而你有M(1<=M<=106)個裝牛奶的容器。請將N瓶牛奶倒進M個容器中並符合以下3點： 1 、同一瓶牛奶不能倒進不同容器。 2 、必須按照輸送帶上的順序挑選牛奶倒進容器。 3 、將牛奶裝進第i個容器後就不能再裝回第(i-1)個容器
題目所求是找出容器中最大值的最小可能的值，也就是說 ，每個容器的容積至少要多少才能用M個容器裝下N瓶牛奶， 是最大值最小化的問題。 輸入直到EOF停止。 題意範例： Sample input： 5 3 //有5瓶牛奶，3個容器 1 2 3 4 5 //每瓶牛奶的容積 3 2 //有3瓶牛奶，2個容器 4 78 9 //每瓶牛奶的容積 Sample output： {(1,2,3) , 4 , 5} 6 {(4,78) , 9} 82
解法：使用binary search、greedy method找出符合條件。建立左界(Left)：所有牛奶瓶容積最大者、右界(Right)：所有牛奶瓶容積總和。 Mid Left Right 容器所裝容積小 容器所裝容積大 1 2 3 4 5 1 2 3 4 5 Left=5 Right = 1+2+3+4+5 = 15
令sum為容器累積總合，bottle為使用過幾個容器。 利用迴圈從第1瓶牛奶跑到第N瓶牛奶： 若sum>mid，則將此迴圈的牛奶倒入下一個容器； 若sum<=mid，則將此迴圈的牛奶倒入此容器，下一瓶牛奶倒入下一個容器。 最後判斷bottle： 若bottle>M，代表所使用容器太多，每個容器容積太小，須將容積增大。往中間值之右的data尋找。 若bottle<=M，代表所使用容器太少，每個容器容積太大，須將容積減小，往中間值之左的data尋找。 最後輸出容器中最大容積的最小可能值，也就是左界，即為答案。 狀況一： 狀況二： 狀況A： 狀況B：
解法範例： N=5，M=3，L=5，R=15，Mid=10 2 3 4 5 狀況二 6+4=10 4 3 2 1 5 Bottle=2
因為bottle<M，往中間值以左尋找，right=mid。 迴圈持續做到Left<Right時跳脫，輸出Left。 Round1: Mid 10 Left 5 Right 15 Round2: Mid 7 Right 10
討論： 1、一開始看不懂題目所求：Your job is to find out the minimal possible capacity of the container which has maximal capacity.看懂之後才了解題目要我們找出容器中最大值的最小可能。