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("/ ");

  }

 }

}