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)


相关推荐

  • 如何画数据库ER图

    如何画数据库ER图一、ER图基本概念ER图分为实体、属性、关系三个核心部分。在ER图中,实体是长方形,属性是椭圆形,关系为菱形。1、实体(entity)即数据模型中的数据对象(即数据表),用长方体来表示,每个实体都有自己的实体成员(entitymember)或者说实体对象(entityinstance),例如学生实体里包括张三、李四等。实体还会细分为弱实体和复合实体,一个实体必须依赖于另一个实…

  • 基于faster-rcnn的目标物体检测_传统的目标检测算法

    基于faster-rcnn的目标物体检测_传统的目标检测算法继RCNN,fastRCNN之后,目标检测界的领军人物RossGirshick在2015年提出fasterRCNN。目标检测速度达到15fps。

    2022年10月13日
  • IntelliJ IDEA v2021.3.5 激活码 3月最新注册码

    IntelliJ IDEA v2021.3.5 激活码 3月最新注册码,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 站长工具之在线检测网页错误

    站长工具之在线检测网页错误网页代码测试工具  没有站长可以保证自己的网页代码完全正确没有任何错误,特别是是否符合W3C标准,你可以通过以下测试来检查网站代码是否正确,无论你是asp的还是php的都可以哟。  1.http://www.htmlhelp.com/tools/validator一个很好的工具,能找出网站语法错误的地方,并标注出来,也可选择对网站上单独的每一页进行单页分析。(强烈推荐)

  • 「旅游信息管理系统」 · Java Swing + MySQL 开发「建议收藏」

    「旅游信息管理系统」 · Java Swing + MySQL 开发「建议收藏」代码写得烂,写博客纯属记录!微信公众号:BugLass码云仓库地址:https://gitee.com/ynavc/tourism_sys源代码及文档打包下载:https://download.csdn.net/download/weixin_44893902/12819432目录一、需求简介:业务流程及系统概念模型如下:游客:业务管理员:旅游业务模型:整体概要设计:二、界面示例:首页:点击报名:如果没有登录提示游客登录登录界面:注册界面:..

  • Python之functools库

    functools库用于高阶函数,指那些作用于函数或者返回其他函数的函数functools提供方法如下:cmp_to_key将老式的比较函数转换为关键字函数,与接收keyfunction的函数

    2021年12月19日

发表回复

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

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