1505 Copying Books

問題概要

mページの本をk人の写本屋が写本する。
各ページにはそれぞれコピーにかかる時間が設定されている。

k人の写本屋を使うために、本を連続する区間k個に分割する。
写本にかかる全体の時間は、それぞれの区間のコピーにかかる時間の最大値である。

写本の時間の最小値を与える区間の分割を求めよ。
それが複数あるときは、1番目の区間を最も短く（それでも複数あるなら2番目の区間を最も短く…以下同様）するような分割を求めよ。

m≦500とする。

解法

区間の和（の最小値（以下ノルマ）は二分法により求まる。
（長さを決め打ちして、長さを超えた時点で区間を切り、それが全部jでk個以下であるかを判定することによりO(mlog Sum)でできる。Sumはページ数の和）

その後、なるべく小さいページ数を先頭から取っていく。
ここでは、先ほどの二分探索の関数を使いまわせる。
すなわち自分以降の人間がすべてノルマ以下かどうかはO(m)で判定できるので、O(m^2)の計算量で題意の分割の仕方が求められる。

ソースコード

int k,m,ans[500],tmp[500];
ll b[500],one;

bool ok(ll lim,int st,int time){
	ll s=0; int cut=0;
	for(int i=st;i<m;i++){
		if(b[i]>lim)return 0;
		if(s+b[i]>lim){
			if(++cut>=time)return 0;
			s=b[i];
		}
		else s+=b[i];
	}
	return 1;
}
void rec(int c,int cut,ll s){
	if(ans[0]>=0)return;
	if(c==m){
		rep(i,m)ans[i]=tmp[i];
		return;
	}
	if(!ok(one,c,k-cut))return;
	
	if(c&&cut<k-1)
	{
		tmp[c-1]=1;
		rec(c+1,cut+1,b[c]);
		tmp[c-1]=0;
	}
	if(s+b[c]<=one)rec(c+1,cut,s+b[c]);
}
int main(){
	int T; scanf("%d",&T);
	rep(U,T){
		scanf("%d%d",&m,&k);
		ll sum=0;
		rep(i,m)scanf("%lld",b+i),sum+=b[i];
		
		ll lo=0,hi=sum,mid;
		while(lo+1<hi){
			mid=(lo+hi)/2;
			if(ok(mid,0,k))hi=mid; else lo=mid;
		}
		one=hi;
		
		rep(i,m)tmp[i]=0; ans[0]=-1;
		rec(0,0,0);
		
		rep(i,m){
			if(i)printf(ans[i-1]?" / ":" ");
			printf("%d",b[i]);
		}
		puts("");
	}
	return 0;
}