POJ 1505 Copying Books(贪心 - 二分 + 最小化最大值)
程序员文章站
2022-03-11 23:30:05
...
题意:给你 m 本书和 k 个人,第 i 本书对应的页数是 a[i],找到一种分配方法使得所有人印刷完后使用的总时间最短(每个人的工作效率相同)。最后输出划分的情况。若有多种划分方法,输出子序列从小到大的情况。
思路:我们先找到如果讲这些书分给 k 个人,那么某个人最多印刷多少页(而题目这个页数要求尽量小)。(最小化最大值),这个最大值范围就是[max(mmin,a[i]),sum+a[i]];我们对这个区间进行二分,判断每一个 mid 需要多少人 cnt,如果 cnt < k,用的人少了(可以增加人来印刷,那么每个人印刷的也就变少了),说明这个最大值还可以更小,否则说明这个最大值太小了。找到这个最大值以后,从后往前我们就可以把所有书分给每一个人。最后如果还有多出来的人,就从前往后的分配。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int Max_n=510;
int a[Max_n];
bool vis[Max_n];
int m,k;
bool check(ll x){
ll sum=0,cnt=0;
for(int i=m;i>=1;i--){//这个工作量用了多少人
sum+=(ll)a[i];
if(sum>x){
sum=(ll)a[i];
cnt++;
}
}
return cnt<k;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&m,&k);
ll mmin=0,mmax=0;
for(int i=1;i<=m;i++){
scanf("%d",&a[i]);
mmin=max((ll)a[i],mmin);
mmax+=a[i];
vis[i]=false;
}
ll l=mmin,r=mmax,ans;
while(l<=r){//找到某个人最多可以印刷的页数(保证这个页数尽量最小)
ll mid=l+(r-l)/2;
if(check(mid)){//用的人少,此页数还可以小
ans=mid;
r=mid-1;
}else{//超出,页数需要变大
l=mid+1;
}
}
ll sum=0,cnt=0;
for(int i=m;i>=1;i--){//根据某个人最多可以做的工作量分配书本
sum+=(ll)a[i];
if(sum>ans){
sum=(ll)a[i];
cnt++;
vis[i]=true;
}
}
for(int i=1;i<=m&&cnt<k-1;i++){//人没有分配够,前面的书每个人印刷一本
if(!vis[i]){
cnt++;
vis[i]=true;
}
}
for(int i=1;i<=m;i++){
printf("%d%c",a[i],i==m?'\n':' ');
if(vis[i]) printf("/ ");
}
}
return 0;
}