[UVa] 11413 Fill the Containers.cpp

#include<cstdio>
using namespace std;

int N,M; // N:牛奶瓶數量  M:容器數量
int n[1000001];   // 牛奶瓶的個別容積

int main()
{
    while (scanf("%d%d",&N,&M)!=EOF){
        int left=0,right=0,mid;
        for (int i=0; i<N; i++) {
            scanf("%d",&n[i]);
            if (n[i]>left) left = n[i];
            right += n[i];
        }

        while (left < right){  //使用二元搜尋找出最小容器的容積能使amount==M
            mid = (left+right)/2;
            int sum=0;    // 用來累積每瓶牛奶的容量
            int amount=0; // 用來計數用了多少容器
            for (int i=0; i<N; i++){
                sum += n[i];
                if (sum > mid) {
                    amount++;
                    sum = n[i];
                }
                else if (sum == mid){
                    amount++;
                    sum = 0;
                }
            }
            if (sum>0) amount++;
            
            if (amount > M) left = mid+1; //如果大於題目規定代表我們的容積太小，導致容器太多
            else right = mid;
        }
        printf("%d\n",left);
    }
    return 0;
}