uva 714——Copying Books

小灰灰 2022-08-10 00:59 152阅读 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 条评论，152人围观）

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

相关阅读

相关 UVA 714 Copying Books （二分）

题意：把一个包含m个正整数的序列划分成k个非空的连续子序列，使得每个正整数恰好属于一个序列。设第i个序列的和为S(i)，要找所有S(i)的最大值尽量小。如有多解，S(1)应

秒速五厘米/ 2024年02月17日 22:47/ 0 赞/ 17 阅读

相关 copies(copies什么意思)

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

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

相关 copy(copy)

copy 是什么意思？复制抄袭，拷贝拷贝，复制版 ![copy(copy)\_copy(copy)][copy_copy_copy_copy] xcopy和cop

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

相关 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 赞/ 211 阅读

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

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

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

相关 C - Book 拓扑排序

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

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

相关 uva 714——Copying Books

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

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

相关 Shallow copy & Deep copy

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

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

相关 The Little Redis Book

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

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

相关 Kernel book

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

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