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=(所有牛奶瓶的容積)。

	#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;
	}

view raw [UVa] 11413 Fill the Containers.cpp hosted with ❤ by GitHub