分制书稿

diggersun · 发表于 2016-2-1 17:17:49

本帖最后由 diggersun 于 2017-10-3 15:06 编辑

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

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

diggersun · 发表于 2017-10-3 15:09:10

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

diggersun · 发表于 2017-10-3 15:13:42

DP的做法是典型的的背包问题变形，若设f[i][j]为前面i本书分成j个人抄时的最少时间，s[i][j]为一个抄第i到第j本书的时间，则转移方程“
f[i][1]=s[1][i]
f[i][j]=min(f[i-k][j-1]+s[i-k+1][i])
看得出这个转移方程和背包问题很相似，套用那个程序的框架即可。
// 1 3 7 8 9 2 4 5 6九个数字按顺序分成三堆，使最大的那一堆最小
#include <iostream>
#include <iomanip>
using namespace std;
int a[10]= {0,1,2,3,4,5,6,7,8,9}; //十堆原始数据
int s[10][10]; //s[i][j]表示第i堆到第j堆共有多少个 DP初始状态不划分的情况
int f[10][4]; //f[i][j]前i个石头被分成j堆得最小值 DP状态
int w[10][4]; //划分点，决策方法
int i,j,k,t1,t2,t,m,p;
int main()
{
for (i=1; i<=9; i++)
{
s[i][i]=a[i];
for (j=i+1; j<=9; j++) s[i][j]=s[i][j-1]+a[j];
}
//输出检查下
cout<<"================s====\n";
for (i=1; i<=9; i++)
{
for (j=1; j<=9; j++) cout<<setw(4)<<s[i][j];
cout<<endl;
}
//初始状态不划分的话就是直接加
for (i=1; i<=9; i++) f[i][1]=s[1][i];
for (j=2; j<=3; j++) //分成2堆开始注意枚举顺序
for (i=j; i<=9; i++) //i显然要大于j
{
m=9999; //最小值初值
for (k=j-1; k<=i-1; k++) //枚举划分点注意取值范围！！！
{
t1=f[k][j-1]; //前面一段 k个数字分成j-1份
t2=s[k+1][i]; //后面一段自成一段
if (t1>t2) t=t1;
else t=t2;//取最大值
if (t<m) m=t,p=k; //记录最小值和位置
}
f[i][j]=m,w[i][j]=p; //DP更新值
}
//检查f数组
cout<<"================f====\n";
for (j=1; j<=3; j++)
{
for (i=1; i<=9; i++) cout<<setw(4)<<f[i][j];
cout<<endl;
}
cout<<f[9][3]<<endl;
cout<<"================w====\n";
for (j=1; j<=3; j++)
{
for (i=1; i<=9; i++) cout<<setw(4)<<w[i][j];
cout<<endl;
}
cout<<f[9][3]<<endl;
}

复制代码

admin · 发表于 2018-4-16 12:58:56

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

#include<iostream>
using namespace std;
const int mn=510;
int a[mn],p[mn];
int m,k;
int i,l,r,mid,s;
bool check(int mid)
{
int kk=1,s=0;
for (int i=1; i<=m; i++)
{
s=s+a[i];
if (s>mid)
{
s=a[i];
kk++;
}
}
return kk<=k;
}
int main()
{
cin>>m>>k;
for (int i=1; i<=m; i++)
{
cin>>a[i];
s+=a[i];
}
l=s/k;
r=s;
bool b=1;
while (l<r)
{
mid=(l+r)/2;
///cout<<l<<' '<<r<<endl;
if (check(mid)) r--;
else l++;
}
///cout<<l<<endl;
s=0;
int kk=k-1;
for (i=m; i>=1; i--)
{
s=s+a[i];
if (s>l)
{
s=a[i];
p[kk]=i;
kk--;
}
}
///for (i=1;i<=k-1;i++) cout<<p[i]<<' ';cout<<endl;
cout<<1<<' ';
for (i=1; i<=k-1; i++) cout<<p[i]<<endl<<p[i]+1<<' ';
cout<<m;
return 0;
}

复制代码

admin · 发表于 2019-8-9 16:19:38

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

		自动登录	找回密码
密码			立即注册