uva 714 - Copying Books（贪心最大值最小化二分）

uva 714 – Copying Books（贪心最大值最小化二分）

全栈程序员-站长 • 2021年12月2日下午10:00 • 未分类 • 阅读 57

大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。

题目描写叙述开头一大堆屁话，我还细致看了半天。。事实上就最后2句管用。意思就是给出n本书然后要分成k份，每份总页数的最大值要最小。问你分配方案，假设最小值同样情况下有多种分配方案，输出前面份数小的，就像字典序输出从小到大一样的意思。

这里用到贪心的方法，定义f(x)为真的条件是满足x为最大值使n本书分成k份，那么就是求x的最小值。怎样确定这个x就是用的二分法，x一定大于0小于全部值的合，不断的二分再推断是否成立，成立就取左半边，不成立说明太小了就取右半边，写的时候还是没有把二分法理解透彻，我还怕会丢失那个值还特意去保存，其实二分法最后结束得出来的x或y（二个数是相等的）就是每份的最大值。而怎样确定这个最大值是否成立就是用贪心的方法，尽量的往右边拓展直到大于最大值的前一个为止。假设份数还没分完就到最后一个了，那就肯定是成立的。反之，假设份数分完了还没到最后一个那就是不成立。

输出的时候还得注意，得从后往前，由于前面的份数得要小，就得从后往前贪心，还有当剩余的跟份数一样的时候就不能贪心了，就要每个都要分开了。这个就自己模拟数据看吧，加一减一的都得跟前面写的有关系。

还有两点要特别注意，求和的时候会超int范围，由于一个最大可达1×10^8，而最多有500个，超过了4×10^9了。所以要用long long。另一点是输出的时候最后一个数字后面不能多打一个空格不然会报PE的。

AC代码：

#include<cstdio>
#include<ctype.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<ctime>
using namespace std;
#define NMAX 505
#define ll long long
int a[NMAX];
int ans[NMAX];
int solve(ll Max,int n,int k)
{
    int i=0,j=0,nct=0;
    ll sum=0;
    while(nct < k)
    {
        sum+=a[j];
        if(sum > Max && i == j) return 0;
        if(sum > Max)
        {
            nct++;
            i = j;
            sum = 0;
        }
        else j++;
        if(j == n) return 1;
    }
    return 0;
}

void path(ll Max,int n,int k)
{
    int nct = 0,i=n-1;
    ll sum=0;
    while(i>0)
    {
        sum+=a[i];
        if(sum > Max)
        {
            sum = 0;
            ans[i] = 1;
            nct++;
        }
        else i--;
        if(i == k-nct-2)
        {
            for(int j = 0; j <= i; j++)
                ans[j] = 1;
            break;
        }
    }
    for(int i = 0; i < n; i++)
    {
        if(i == n-1) printf("%d",a[i]);
        else printf("%d ",a[i]);
        if(ans[i]) printf("/ ");
    }
    printf("\n");
}

int main()
{
    int i,n,k,m;
    scanf("%d",&n);
    while(n--)
    {
        memset(ans,0,sizeof(ans));
        scanf("%d%d",&m,&k);
        ll sum = 0;
        for(i = 0; i < m; i++)
        {
            scanf("%d",&a[i]);
            sum += a[i];
        }
        ll x=0,y=sum,z;
        while(x<y)
        {
            z = x+(y-x)/2;
            if(solve(z,m,k))
                y = z;
            else x = z+1;
        }
        path(x,m,k);
    }
    return 0;
}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118673.html原文链接：https://javaforall.net