UVa 714 Copying Books

本題題目連結
想法：
　　這題跟UVa 11413 Fill the Containers很類似，題目給定M本書及K個員工(1<=K<=M<=500)，每本書有不同的頁數，同本書只能分配給同個員工，我們用二分搜尋找出每個人的工作量(頁數)的上限，(題目要求工作量越少越好，但如果太少就需要>K個員工)。此外如果有多組解的情況，index越大的員工所分配的書要盡量的多，因此分配書的時候index從後面開始，但注意分配時每個人至少要有一本書，因此如果(剩下的書<=剩下的人)，就算那個人還沒分完，也要直接換下一個人。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int M, K;
	int p[501];
	int ans[501][501],n[501]; // n is the index of ans[i];
	int main()
	{
	int N;
	scanf("%d",&N);
	while (N--){
	scanf ("%d%d",&M,&K);
	long long int Min=0,Max=0,mid;
	for (int i=0;i<M;i++) {
	scanf("%d",&p[i]);
	if (p[i] > Min) Min=p[i];
	Max += p[i];
	}
	while (Min < Max){
	int amount=1;
	long long int sum=0;
	mid = (Min+Max)/2;
	for (int i=0;i<M;i++){
	if (sum+p[i] > mid){
	amount++;
	sum = 0;
	}
	sum += p[i];
	}
	if (amount > K) Min = mid+1;
	else Max = mid;
	}
	fill (n,n+501,0);
	long long sum = 0;
	// 因為如果有多組解，後面的人要分配多一點書，因此i,j從後面開始
	for (int i=M-1, j=K-1; i>=0; i--){ // i: book index, j: scriber index
	if (sum+p[i] > Max || j>i){ // j>i: 因為每個人都至少要有一本書
	j--;
	sum = 0;
	}
	sum += p[i];
	ans[j][n[j]++] = p[i];
	}
	for (int i=0; i<K; i++){
	for (int j=n[i]-1; j>=0; j--){
	if (i!=0 || j!=n[0]-1) printf(" ");
	printf("%d",ans[i][j]);
	}
	if (i != K-1) printf(" /");
	}
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 714 Copying Books.cpp hosted with ❤ by GitHub