分制书稿

diggersun

现在要把m本有顺序的书分给k给人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。
输入格式：
第一行两个整数m，k；（k≤m≤500）
第二行m个整数，第i个整数表示第i本书的页数。
输出格式：
一个整数抄写页数最多的人用去的时间。

题解：此题时很经典的题目，有两种经典的解法，都值得学习，一个是二分法，一个是DP法。

admin

这个题目里面有很多的隐患，大家要注意！

admin

另外一种解法就是整体二分，因为这显然是一个单调递增的函数模型，套用二分，起点：总页数除以人数 终点：总页数。然后求中点，判断是否可行，可以的话，往下找，不行的话，往上找，直到LR重叠找不到为止。

1. #include<iostream>
   
2. using namespace std;
   
3. const int mn=510;
   
4. int a[mn],p[mn];
   
5. int m,k;
   
6. int i,l,r,mid,s;
   
7. bool check(int mid)
   
8. {
   
9.     int kk=1,s=0;
   
10.     for (int i=1; i<=m; i++)
    
11.     {
    
12.         s=s+a[i];
    
13.         if (s>mid)
    
14.         {
    
15.             s=a[i];
    
16.             kk++;
    
17.         }
    
18.     }
    
19.     return kk<=k;
    
20. }
    
21. int main()
    
22. {
    
23.     cin>>m>>k;
    
24.     for (int i=1; i<=m; i++)
    
25.     {
    
26.         cin>>a[i];
    
27.         s+=a[i];
    
28.     }
    
29.     l=s/k;
    
30.     r=s;
    
31.     bool b=1;
    
32.     while (l<r)
    
33.     {
    
34.         mid=(l+r)/2;
    
35.         ///cout<<l<<' '<<r<<endl;
    
36. 
    
37.         if (check(mid)) r--;
    
38.         else  l++;
    
39.     }
    
40.     ///cout<<l<<endl;
    
41.     s=0;
    
42.     int kk=k-1;
    
43.     for (i=m; i>=1; i--)
    
44.     {
    
45.         s=s+a[i];
    
46.         if (s>l)
    
47.         {
    
48.             s=a[i];
    
49.             p[kk]=i;
    
50.             kk--;
    
51.         }
    
52. 
    
53.     }
    
54.     ///for (i=1;i<=k-1;i++) cout<<p[i]<<' ';cout<<endl;
    
55.     cout<<1<<' ';
    
56.     for (i=1; i<=k-1; i++) cout<<p[i]<<endl<<p[i]+1<<' ';
    
57.     cout<<m;
    
58.     return 0;
    
59. }
    

复制代码

diggersun

1. DP的做法是典型的的背包问题变形，若设f[i][j]为前面i本书分成j个人抄时的最少时间，s[i][j]为一个抄第i到第j本书的时间，则转移方程“
   
2. f[i][1]=s[1][i]
   
3. f[i][j]=min(f[i-k][j-1]+s[i-k+1][i])
   
4. 看得出这个转移方程和背包问题很相似，套用那个程序的框架即可。
   
5. 
   
6. // 1 3 7 8 9 2 4 5 6九个数字按顺序分成三堆，使最大的那一堆最小
   
7. #include <iostream>
   
8. #include <iomanip>
   
9. using namespace std;
   
10. int a[10]= {0,1,2,3,4,5,6,7,8,9}; //十堆原始数据
    
11. int s[10][10]; //s[i][j]表示第i堆到第j堆共有多少个 DP初始状态  不划分的情况
    
12. int f[10][4];  //f[i][j]前i个石头被分成j堆得最小值 DP状态
    
13. int w[10][4]; //划分点，决策方法
    
14. int i,j,k,t1,t2,t,m,p;
    
15. int main()
    
16. {
    
17.     for (i=1; i<=9; i++)
    
18.     {
    
19.         s[i][i]=a[i];
    
20.         for (j=i+1; j<=9; j++) s[i][j]=s[i][j-1]+a[j];
    
21.     }
    
22.     //输出检查下
    
23.     cout<<"================s====\n";
    
24.     for (i=1; i<=9; i++)
    
25.     {
    
26.         for (j=1; j<=9; j++) cout<<setw(4)<<s[i][j];
    
27.         cout<<endl;
    
28.     }
    
29. 
    
30.     //初始状态 不划分的话就是直接加
    
31.     for (i=1; i<=9; i++) f[i][1]=s[1][i];
    
32. 
    
33.     for (j=2; j<=3; j++) //分成2堆开始    注意枚举顺序
    
34.         for (i=j; i<=9; i++) //i显然要大于j
    
35.         {
    
36.             m=9999;  //最小值初值
    
37.             for (k=j-1; k<=i-1; k++) //枚举划分点  注意取值范围！！！
    
38.             {
    
39.                 t1=f[k][j-1];  //前面一段 k个数字分成j-1份
    
40.                 t2=s[k+1][i]; //后面一段 自成一段
    
41.                 if (t1>t2) t=t1;
    
42.                 else t=t2;//取最大值
    
43.                 if (t<m) m=t,p=k;    //记录最小值和位置
    
44.             }
    
45.             f[i][j]=m,w[i][j]=p; //DP更新值
    
46.         }
    
47. 
    
48. 
    
49.     //检查f数组
    
50.     cout<<"================f====\n";
    
51.     for (j=1; j<=3; j++)
    
52.     {
    
53.         for (i=1; i<=9; i++) cout<<setw(4)<<f[i][j];
    
54.         cout<<endl;
    
55.     }
    
56. 
    
57.     cout<<f[9][3]<<endl;
    
58. 
    
59.     cout<<"================w====\n";
    
60.     for (j=1; j<=3; j++)
    
61.     {
    
62.         for (i=1; i<=9; i++) cout<<setw(4)<<w[i][j];
    
63.         cout<<endl;
    
64.     }
    
65. 
    
66.     cout<<f[9][3]<<endl;
    
67. 
    
68. }
    

复制代码

diggersun

看到此题的最大值最小我们一般马上会想到二分法，二分左边界是所有数字的算术平均数，右边界可以设为所有的数字的和，枚举中点，看能否符合要求，符合的话，往小的方向寻找，不符合的话，往大的方向寻找。