华师一附中OI组

标题: 分制书稿 [打印本页]
作者: diggersun    时间: 2016-2-1 17:17
标题: 分制书稿
本帖最后由 diggersun 于 2017-10-3 15:06 编辑

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

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

作者: diggersun    时间: 2017-10-3 15:09
看到此题的最大值最小我们一般马上会想到二分法，二分左边界是所有数字的算术平均数，右边界可以设为所有的数字的和，枚举中点，看能否符合要求，符合的话，往小的方向寻找，不符合的话，往大的方向寻找。
作者: diggersun    时间: 2017-10-3 15:13
  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. 看得出这个转移方程和背包问题很相似，套用那个程序的框架即可。

  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.     }

  30.     //初始状态 不划分的话就是直接加
  31.     for (i=1; i<=9; i++) f[i][1]=s[1][i];

  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.         }


  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.     }

  57.     cout<<f[9][3]<<endl;

  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.     }

  66.     cout<<f[9][3]<<endl;

  68. }
复制代码
作者: admin    时间: 2018-4-16 12:58
另外一种解法就是整体二分，因为这显然是一个单调递增的函数模型，套用二分，起点：总页数除以人数 终点：总页数。然后求中点，判断是否可行，可以的话，往下找，不行的话，往上找，直到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;

  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.         }

  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. }
复制代码


作者: admin    时间: 2019-8-9 16:19
这个题目里面有很多的隐患，大家要注意！



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2