欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 1505 Copying Books(贪心 - 二分 + 最小化最大值)

程序员文章站 2022-03-11 23:30:05
...

链接:http://poj.org/problem?id=1505

POJ 1505	Copying Books(贪心 - 二分 + 最小化最大值)
  题意:给你 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;
}