uva 714——Copying Books

小灰灰 2022-08-10 00:59 139阅读 0赞

题意：把一个m个整数的序列划分成k个连续非空的子序列，使得子序列和的最大值最小。

思路：二分。遇到最大值最小大多都二分了，让划分的子序列都不超过x，根据x来judge最终结果k个是多还是少，然后二分来调整x直到出现k个序列。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    #define int long long
    ll m,k,v[505],c[505];
    bool judge(ll x)
    {
        ll p=0,q=0;
        for (int i=0;i<m;i++)
        {
            p+=v[i];
            if (v[i]>x) return false;
            if (p>x){p=v[i];q++;}
        }
        if (q>k-1) return false;
        return true;
    }
    
     main()
    {
        int T;
        scanf("%d",&T);
        while (T--)
        {
            int s=0,len;memset(c,0,sizeof(c));
            scanf("%lld %lld",&m,&k);
            for (int i=0;i<m;i++) scanf("%lld",&v[i]),s+=v[i];
            int l=0,r=s,mid;
            while (l<r)
            {
                mid=l+(r-l)/2;
                if (!judge(mid)) l=mid+1;
                else r=mid;
            }
            len=s=0;
            for (int i=m-1;i>=0;i--)
            {
              s+=v[i];
              if (s>r||k-len==i+2){s=v[i];c[len++]=i;}
            }
            len=k-2;
            for (int i=0;i<m;i++)
            {
                printf("%lld",v[i]);
                if (i!=m-1) printf(" ");
                if (len>=0&&i==c[len]) printf("/ "),len--;
            }
            puts("");
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，139人围观）

还没有评论，来说两句吧...

相关阅读

相关 copies(copies什么意思)

copies是什么意？copies是什么意思 copies 英\['kɒpɪz\] 美\['kɒpɪz\] n. 文案; 抄本，副本，复制本\[品\]，摹本; 拷贝

╰半橙微兮°/ 2023年09月26日 13:12/ 0 赞/ 26 阅读

相关 postgresql copy from、copy to

官网：[http://postgres.cn/docs/12/sql-copy.html][http_postgres.cn_docs_12_sql-copy.html] 参

心已赠人/ 2022年10月17日 00:50/ 0 赞/ 188 阅读

相关（四十四）：Open-book Video Captioning with Retrieve-Copy-Generate Network

（四十四）：Open-book Video Captioning with Retrieve-Copy-Generate Network 手写笔记出处：

缺乏、安全感/ 2022年09月04日 07:53/ 0 赞/ 133 阅读

相关 C - Book 拓扑排序

[https://codeforces.com/contest/1573/problem/C][https_codeforces.com_contest_1573_proble

谁践踏了优雅/ 2022年08月28日 12:43/ 0 赞/ 174 阅读

相关 uva 714——Copying Books

题意：把一个m个整数的序列划分成k个连续非空的子序列，使得子序列和的最大值最小。思路：二分。遇到最大值最小大多都二分了，让划分的子序列都不超过x，根据x来judg

小灰灰/ 2022年08月10日 00:59/ 0 赞/ 140 阅读

相关 An R "meta" book

(This article was first published on [Revolutions][], and kindly contributed to [R-blog

﹏ヽ暗。殇╰゛Y/ 2022年08月08日 00:39/ 0 赞/ 2 阅读

相关 Shallow copy & Deep copy

面向对象编程语言都提供了内存中对象的复制能力，Java语言提供了对象的浅拷贝和深拷贝。浅拷贝（Shallow copy）：复制一个对象时，如果它的一个属性是引用，则复制

青旅半醒/ 2022年06月16日 11:11/ 0 赞/ 178 阅读

相关 The Little Redis Book

偶然间发现了Redis的这本书，和拥有这本书的网站，感觉相当不错，一个突来的亮点，记录下来以后慢慢看。 The goal of this book is to build t

墨蓝/ 2022年06月12日 00:55/ 0 赞/ 152 阅读

相关 Setup Mac Book Pro

原则：阅读./configure --help的内容一般就能解决安装过程中的问题。 1. 为Dictionary安装中文词典 Linux下的词典StarDict有众多词典

川长思鸟来/ 2021年12月22日 10:39/ 0 赞/ 224 阅读

相关 Kernel book

Linux Kernel Development by Robert Love[ http://www.beginnersheap.com/download-page/

╰半夏微凉°/ 2021年09月22日 16:18/ 0 赞/ 249 阅读