UVA 714 Copying Books （二分）

秒速五厘米 2024-02-17 22:47 17阅读 0赞

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

如有多解，S(1)应尽量小。如果仍有多解，S(2)应尽量小，以此类推。

思路：通过二分找到一个最小x ，使得对任意S(i)<=x，时间复杂度O(logM)，再通过从右到左的扫描即可完成。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn = 500+10;
    typedef long long LL;
    int m,k,f[maxn];
    
    int solve(LL M){
    	LL done = 0;
    	int cnt = 0;
    	for(int i = 0; i < m; i++){
    		if(done + f[i] > M){
    			done = f[i];
    			cnt++ ;
    		}
    		else done += f[i];
    	}
    	return cnt+1 ;
    }
    
    int scribe[maxn];
    
    void print(LL l){
    	memset(scribe,0,sizeof(scribe));
    	LL done = 0;
    	int remain = k - 1;
    	for(int i = m-1; i >= 0; i--){
    		if(done + f[i] > l || i + 1 <= remain){
    			done = f[i];
    			scribe[i] = 1;
    			remain--;
    		}
    		else done += f[i];
    	}
    	
    	for(int i = 0; i < m-1; i++){
    		printf("%d ",f[i]);
    		if(scribe[i]) printf("/ ");
    	}
    	printf("%d\n",f[m-1]);
    }
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    	    scanf("%d%d",&m,&k);
    	    int Max = 0;
    	    LL tol = 0;
    	    for(int i = 0; i < m; i++){
    	    	scanf("%d",&f[i]);
    	    	Max = max(Max,f[i]);
    	    	tol += f[i];
    		}
    		
    		LL l = Max ,r = tol;
    		while(l < r){
    			LL M = l + (r - l)/2;
    			if(solve(M) <= k)r = M;
    			else l = M + 1;
    		}
    		
    		print(l);
    		
    	}
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 UVA 714 Copying Books （二分）

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

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

相关 uva11300分金币随机选择算法

题意：ｎ个人围成一圈，每个人都有一些硬币，，每个人只能给左右相邻的人硬币，问最少交换几个硬币，使每个人硬币一样多； //没用随机选择算法也可以过 /

矫情吗；*/ 2024年02月17日 21:21/ 0 赞/ 64 阅读

相关 Quadtrees UVA 297 四分树

// 2 1 // 3 4 对于四分树来说，给出了它的先序序列就可以确定整棵树了，因为对任意一个节点不是叶子就是父节点，对于一个父节点一定有四个子节点（就和完全二叉树一样，

以你之姓@/ 2024年02月17日 18:53/ 0 赞/ 49 阅读

相关 copy(copy)

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

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

相关（四十四）：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 阅读

相关 uva 714——Copying Books

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

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

相关 UVA 11729-Commando War（排序分任务）

Commando War “Waiting for orders we held in the wood, word from the front never came

桃扇骨/ 2022年07月15日 01:54/ 0 赞/ 71 阅读

相关 book_effective Python_59个有效办法（二）

二函数尽量用异常来表示特殊情况而不要返回None 如何在闭包里使用外围作用域中的变量

た入场券/ 2022年06月13日 23:24/ 0 赞/ 52 阅读

相关 Help is needed for Dexter UVA - 11384（二分）

本来抱着wa一发的心态写写，没想到过了。算是一种二分吧。　![1445856-20190418213032217-468402131.png][] 也就是说，减数取太

系统管理员/ 2021年09月29日 21:56/ 0 赞/ 248 阅读

相关 Kernel book

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

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