17.小朋友分糖果.
N堆糖果從左到右排成一行,編號為1到N,用一個(gè)數(shù)組表示每堆糖果的數(shù)量,其中a(i)表示第i堆糖果的數(shù)量.有K個(gè)小朋友依次從左到右取光連續(xù)的若干堆糖果.
例:有9堆糖果,數(shù)量依次是1,2,3,4,5,6,7,8,9,共有3個(gè)小朋友.
取法一:第一個(gè)小朋友取走1+2+3=6顆,第二個(gè)小朋友取走4+5+6+7=22顆,第三個(gè)小朋友取走8+9=17顆,則三個(gè)小朋友取得的最大值是22;
取法二:第一個(gè)小朋友取走1+2+3+4=10顆,第二個(gè)小朋友取走5+6+7=18顆,第三個(gè)小朋友取走8+9=17顆,則三個(gè)小朋友取得的最大值是18;
取法三:第一個(gè)小朋友取走1+2+3+4+5=15顆,第二個(gè)小朋友取走6+7=13顆,第三個(gè)小朋友取走8+9=17顆,則三個(gè)小朋友取得的最大值是17;
在以上三種取法中,三個(gè)最大值(22,18,17)中的最小值是17.
現(xiàn)在設(shè)計(jì)一個(gè)程序,求所有可能的方案的最大值的最小值是多少,請?jiān)趧澗€處填入合適的代碼.
算法思想簡述:設(shè)Max為數(shù)量最多的一堆糖果的數(shù)量,S為所有糖果的數(shù)量總和,Ans為該問題的答案,其中Max<=Ans<=S.可以將Max,Max+1,Max+2,…,S-1,S序列中的每一個(gè)值逐一驗(yàn)證,驗(yàn)證方法為:以當(dāng)前值為當(dāng)前分配方案中小朋友得到的最大值,是否可以將糖果分給K個(gè)小朋友.在所有可行的值中,查找最小的值,即為Ans.觀察可以發(fā)現(xiàn),Max,Max+1,Max+2,…,S-1,S是一個(gè)有序的序列,可以使用對分查找找到Ans.