POJ1505誊抄书籍

Posted on | In |

问题描述

• 有 m 本书需要誊抄, 每本书的页数分别是 (p1, p2, …, pm)

• 有 k (k <= m) 个抄写员负责誊抄这些书籍

• 任 务

• 将这些书分成 k 份, 每本书必须只分给一个抄写员

• 每个抄写员至少分到一本

• 要求每个抄写员分到的书的编号是连续的

• 即存在一个连续升序数列 0=b0＜b1＜b2＜…＜bk-1＜bk=m

这样, 第 i 号抄写员得到的书稿是从 bi-1+1 到第 bi 本书

image
image
iamge
image
image
image

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include <stdio.h>
#include<algorithm>
using namespace std;
int m,k;
int a[1000];
////当前处理到第book本书, 第scriber堆, 当前堆的页数为now, 每堆页数不能超过ans
void print(int book,int ans,int scriber,long long now){
	bool spec=false;
	if(book<0) return;
    //当前处理到第sriber堆，还剩book(scriber-1)本书
    //因为每个抄写员至少分得一本 所以要新建一堆
    //如果没有book=scriber-1这句 
    //输出情况会是100 100/ 100 100 /100
    //而不会有 100 / 100 /100 /100 100
		if(book==scriber-1||now+a[book]>ans){
			print(book-1,ans,scriber-1,a[book]);
			spec=true;
		}	
		else print(book-1,ans,scriber,now+a[book]);
	
	if(book==0) printf("%d",a[book]);
	else printf(" %d",a[book]);
	if(spec) printf(" /");

} 

bool check(long long x){
	long long now=0;
	int s=0;
	for(int i=m-1;i>=0;i--){
		if(a[i]+now>x) {
			s++;
			now=a[i];
		}
		else now+=a[i];
	}
	if(now>0) s++;//别忘了最后一堆
	if(s>k) return false;
	else return true; 
	
	
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
	//m本书，k个抄写员 
	 scanf("%d%d",&m,&k);
	int sum=0;
	long long left=0;
	for(int i=0;i<m;i++)
	{
		cin>>a[i];
		sum+=a[i];
		if(a[i]>left) left=a[i];//!! left不能写成a[m-1]最多页的一本书不一定是最后一本 
	}
//不能写sort(a,a+m) left=a[m-1] 这样会改变原来书的连续性 违反题意 
	long long right=sum,ans;
	while(left<=right){
 long long mid=(left+right)/2;
	if(check(mid)){
		ans=mid;
		right=mid-1;
	}
	else left=mid+1;
}
	print(m-1,left,k-1,0);	
	cout<<endl; 
}
}