uva 714 – Copying Books(贪心 最大值最小化 二分)

uva 714 – Copying Books(贪心 最大值最小化 二分)

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

题目描写叙述开头一大堆屁话,我还细致看了半天。。事实上就最后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;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118673.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • web.xml的加载过程配置详解

    web.xml的加载过程配置详解一:web.xml加载过程  简单说一下,web.xml的加载过程。当我们启动一个WEB项目容器时,容器包括(JBoss,Tomcat等)。首先会去读取web.xml配置文件里的配置,当这一步骤没有出错并且完成之后,项目才能正常的被启动起来。  启动WEB项目的时候,容器首先会去读取web.xml配置文件中的两个节点:和如图:    紧接着,容器创建一个Serv

  • unity协程简介[通俗易懂]

    unity协程简介[通俗易懂]在Unity中,一般的方法都是顺序执行的,一般的方法也都是在一帧中执行完毕的,当我们所写的方法需要耗费一定时间时,便会出现帧率下降,画面卡顿的现象。当我们调用一个方法想要让一个物体缓慢消失时,除了在Update中执行相关操作外,Unity还提供了更加便利的方法,这便是协程。在通常情况下,如果我们想要让一个物体逐渐消失,我们希望方法可以一次调用便可在程序后续执行中实现我们想要的效果。我们希望代码…

  • vim解决中文乱码问题

    vim解决中文乱码问题

  • spssk均值聚类报告_K均值聚类

    spssk均值聚类报告_K均值聚类机器学习中的k均值聚类属于无监督学习,所谓k指的是簇类的个数,也即均值向量的个数。算法初始状态下,要根据我们设定的k随机生成k个中心向量,随机生成中心向量的方法既可以随机从样本中抽取k个样本作为中心向量,也可以将中心向量固定在样本的维度范围之内,避免中心向量过偏远离大多数样本点。然后每个样本点需要与k个中心向量分别计算欧氏距离,取欧氏距离最小的中心向量作为该样本点的簇类中心,当第一轮迭代完成之后,…

    2022年10月28日
  • Windows宝塔面板彻底卸载_宝塔面板怎么样

    Windows宝塔面板彻底卸载_宝塔面板怎么样宝塔面板安装与卸载

  • Atom动态代码插件Activate Power Mode常用设置[通俗易懂]

    Atom动态代码插件Activate Power Mode常用设置[通俗易懂]相信用过Atom的人都知道它很方便,那么小编在这就介绍下ActivatePowerMode插件的一些实用设置如下:效果的起步阈值:刚装上插件后,效果是你按了20个代码后才有动态效果,在这里可以修改为立马有动态效果目录:Setting/ComboMode中找ComboMode-ActivationThreshold动态效果的声音调节:小编吐槽以下,我网上百度了下怎么调节声音大小,结果就没

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号