【基礎算法】 書的複制

問題 D(1233): 【基礎算法】 書的複制

時間限制: 1 Sec   記憶體限制: 64 MB

題目描述

現在要把m本有順序的書分給k給人複制（抄寫），每一個人的抄寫速度都一樣，一本書不允許給兩個（或以上）的人抄寫，分給每一個人的書，必須是連續的，比如不能把第一、第三、第四本書給同一個人抄寫。 現在請你設計一種方案，使得複制時間最短。複制時間為抄寫頁數最多的人用去的時間。

輸入

第一行兩個整數m，k；（k≤m≤500） 第二行m個整數，第i個整數表示第i本書的頁數。

輸出

共k行，每行兩個整數，第i行表示第i個人抄寫的書的起始編号和終止編号。k行的起始編号應該從小到大排列，如果有多解，則盡可能讓前面的人少抄寫。

樣例輸入

(如果複制到控制台無換行，可以先粘貼到文本編輯器，再複制)

9 3
1 2 3 4 5 6 7 8 9
      

樣例輸出

1 5
6 7
8 9      

談談思路

#include<cstdio>
int m,k,i,a[505],b[505][3],r,j,s,t;
int main()
{
	scanf("%d%d",&m,&k);
	for(i=1;i<=m;i++)
	{	
		scanf("%d",&a[i]);
		r+=a[i];//二分右端點為所有的頁數的和
	}
	int l=0;
	while(l+1<r)
	{
		int mid=(l+r)/2;
		s=0;t=1;//t為mid頁數的抄寫人數，s為相鄰頁數的目前相加的和
		for(i=m;i>0;i--)
		{
			s+=a[i];
			if(s>mid)
			{
				s=a[i];
				t++;
			}
		}
		if(t>k)
			l=mid;
		else
			r=mid;
	}
	s=0;b[k][2]=m;j=k;//s為相鄰頁數的目前相加的和，j表示第j個人，b數組包含所有的人抄寫的書的起始編号和終止編号
	for(i=m;i>0;i--)
	{
		s+=a[i];
		if(s>r)
		{
			s=a[i]; 
			b[j][1]=i+1;//因為大于r,是以上一個數就為第j個人的終止編号
			b[--j][2]=i;//而這一個數就為下一個人的起始編号
		}
	}
	b[1][1]=1;
	for(i=1;i<=k;i++)
		printf("%d %d\n",b[i][1],b[i][2]);
}
           

！！！！注意：

1、二分中不能正序查找。

2、s必須小于r（r>l）