Description
Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so calledscribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.
Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered ) that may have different number of pages (
) and you want to make one copy of each of them. Your task is to divide these books among k scribes,
. Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers
such that i-th scriber gets a sequence of books with numbers between bi-1+1 and bi. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.
The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, . At the second line, there are integers
separated by spaces. All these values are positive and less than 10000000.
For each case, print exactly one line. The line must contain the input succession divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character (`/') to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash.
If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.
2 9 3 100 200 300 400 500 600 700 800 900 5 4 100 100 100 100 100
100 200 300 400 500 / 600 700 / 800 900 100 / 100 / 100 / 100 100
題意：要抄N本書，編號為1,2,3...N, 每本書有1<=x<=10000000頁， 把這些書分配給K個抄寫員，要求分配給某個抄寫員的那些書的編號必須是連續的。每個抄寫員的速度是相同的，求所有書抄完所用的最少時間的分配方案。如果有多種分配方案，盡可能的往前面劃分
解題思路：
1.要求最少時間，取決於抄書最多的人。所以只有抄書最多的人，抄的盡可能少，時間才最少。所以這題就變成了使最大值盡量小的問題了。
下面考慮下一個問題，哪個值是最大序列的最小值呢？我們不妨考慮下最大序列的范圍，不難想到它是 最小頁數min——整個序列之和sum 。我們要從中找到他的最大序列的最小值。因為每本書有有1<=x<=10000000頁，所以sum絕逼會大於int，查找這個范圍也是巨大的。為了不超時，所以就用二分法.......（其實為什麼用2分法，我也不知道，自己想的一個牽強的理由。反正書上是說用二分法....）
2. 然後就是用二分法縮小范圍直到找到那個最大序列的最小值，這裡用x表示..... 腫麼找x呢！你可以用二分法，先求x范圍的中點，然後從序列a[0]開始求和，如果加到第i個數
發現它大於中點，說明x在後半段，變左端點，反之，說明在在前半段，變右端點。最後找到x。
3. 最後就簡單了，只需要標記，然後輸出就好了....
這裡給兩個代碼，第一個是答案代碼，第二個是我測試加的一些輸出..... 也許對理解有些幫助........
1.正確代碼：
1 #include <stdio.h>
2 #include <string.h>
3 #define LL long long
4 int min=0,m,k,a[505],ans[505];
5 LL sum=0;
6 bool juge(LL x)
7 {
8 LL sum2=0;
9 int t=k;
10 for(int i=0;i<m;i++){
11 sum2+=a[i];
12 if(sum2>x){
13 t--; //記錄劃得次數
14 i--;
15 sum2=0;
16 }
17 if(!t){ // 如果劃完了
18 if(i!=m-1) return false; //劃完了，但是沒有劃到最後一個，說明最大序列的最小值比現在的x大.....
19 else return true;
20 }
21 }
22 return true;
23 }
24
25 void zhaox()
26 {
27 memset(ans,0,sizeof(ans));
28 LL l=min,r=sum,mid;
29 while(l<r){ //當左端點等於右端點就確定了一個數x
30 mid=(r+l)/2; //中點
31 if(juge(mid)) //判斷是在中點的哪邊
32 r=mid;
33 else
34 l=mid+1;
35 }
36 LL sum3=0;
37 for(int i=m-1;i>=0;i--){
38 sum3+=a[i];
39 if(sum3>r){
40 sum3=0;
41 k--;
42 ans[++i]=1; //標記
43 }
44 }
45
46 while(k>1){ //如果沒有劃完，接著劃，這裡按照題意，需要使前面的盡可能小，所以從前面開始劃..（從1開始是因為輸出的關系吧，我猜的，還不是很明白...）
47 for(int i=1;i<m;i++){
48 if(!ans[i]) {
49 ans[i]=1; //標記
50 k--;
51 break;
52 }
53 }
54 }
55 //print();
56 printf("%d",a[0]);
57 for(int i=1;i<m;i++){
58 if(ans[i]) printf(" /");
59 printf(" %d",a[i]);
60 }
61 printf("\n");
62 }
63 int main()
64 {
65 int T;
66 scanf("%d",&T);
67 while(T--){
68 scanf("%d%d",&m,&k);
69 for(int i=0;i<m;i++){
70 scanf("%d",&a[i]);
71 if(min>a[i]) min=a[i]; //計算范圍
72 sum+=a[i]; //計算范圍
73 }
74 zhaox(); // 找x的函數加上輸出的部分
75 }
76 return 0;
77 }
實驗代碼：
1 #include <stdio.h>
2 #include <string.h>
3 #define LL long long
4 int min=0,m,k,a[505],ans[505];
5 LL sum=0,j=1;
6 bool juge(LL x)
7 {
8 printf("\n第%d次\n",j++);
9 LL sum2=0;
10 int t=k;
11 for(int i=0;i<m;i++){
12 sum2+=a[i];
13 if(sum2>x){
14 sum2=0;
15 t--;
16 i--;
17 printf("%d ",a[i]);
18 }
19
20 if(!t){
21 if(i!=m-1) {printf("\n%d\n",0); printf("%d %d\n",a[i],a[m-1]); return false;}
22 else {printf("\n%d\n",1); return true;}
23 }
24 }
25 printf("\n%d\n",1);
26 return true;
27 }
28
29 void zhaox()
30 {
31 memset(ans,0,sizeof(ans));
32 LL l=min,r=sum,mid;
33 while(l<r){
34 mid=(r+l)/2;
35 printf("\nx=%d\n",r);
36 if(juge(mid))
37 r=mid;
38 else
39 l=mid+1;
40 }
41 LL sum3=0;
42 for(int i=m-1;i>=0;i--){
43 sum3+=a[i];
44 if(sum3>r){
45 sum3=0;
46 k--;
47 ans[++i]=1;
48 }
49 }
50 while(k>1){
51 for(int i=1;i<m;i++){
52 if(!ans[i]) {
53 ans[i]=1;
54 k--;
55 break;
56 }
57 }
58 }
59 //print();
60 printf("%d",a[0]);
61 for(int i=1;i<m;i++){
62 if(ans[i]) printf(" /");
63 printf(" %d",a[i]);
64 }
65 printf("\n");
66 }
67 int main()
68 {
69 int T;
70 scanf("%d",&T);
71 while(T--){
72 scanf("%d%d",&m,&k);
73 for(int i=0;i<m;i++){
74 scanf("%d",&a[i]);
75 if(min>a[i]) min=a[i];
76 sum+=a[i];
77 }
78 zhaox();
79 }
80 return 0;
81 }
