PKU 1505 Copying Books

#include<stdio.h>

#include<iostream>

#include<string.h>

using namespace std;

const int lmax=505;

int n,m,book[lmax];

bool used[lmax];

int cal(int len)//返回的是段数

{

 int i,num=1,sum=0;

 //num用来标记段数,对于不同的L值,都是先进行更新

 memset(used,0,sizeof(used));

 for(i=n-1;i>=0;i--)

 if(sum+book[i]>len)//大于,则须在I处断开,即任何一段之和要小于len

 {

  used[i+1]=true;//标记此处要段开

  sum=book[i];

  num++;//开始新的一段

 }

 else sum+=book[i];//小于,仍属于此段

 return num;

}

int main()

{

 int T,i;

 scanf("%d",&T);

 while(T--)

 {

  scanf("%d%d",&n,&m);

  int left,right,mid,num;

  for(left=right=i=0;i<n;i++)//

  {

   scanf("%d",book+i);

   left=max(left,book[i]);

   right+=book[i];

  }

  while(left<right)

  {

   mid=left+(right-left)/2;

   if(cal(mid)<=m) right=mid;//如果以MID为最大值,而得到的段数小于等于m,说明MID值太大了

   else left=mid+1;//否则MID值太小,使得段数大于m

  }

  //求出以MAX为最大值所能够得到的段数(从后至前,因为题目要求使得前面的任务越小越好)

  num=cal(right);//这里为什么又要从新计算一遍,是为了根据二分的结果,给used[]设定值

  for(i=1;i<n&&num<m;i++)//处理前面的段

  if(used[i]==false) //多余的段数全部用在最前面,使得前面的工人任务数是最优解中最少的

  {

   used[i]=true;

   num++;

  }

  for(i=0;i<n;i++)

  {

   printf("%d%c",book[i],i==n-1?'\n':' ');

   if(used[i+1]) printf("/ ");

  }

 }

}