数组分段使得每个段的元素之和最大的最小

阳光穿透心脏的1/2处 2022-02-20 12:13 190阅读 0赞

# 题目描述 #

给 n 个正整数 a\_1 … a\_n, 将 n 个数排成一列后分割成 m 段, 每一段的分数为这段内所有数的和, 该次分割的分数被记为 m 段分数的最大值.  
问所有分割方案中分割分数的最小值是多少?

# 思路 #

二分搜索.  
首先定义一个函数 check, 返回布尔型, 用来检查能不能用一个数 x 来将数组分割成 m 份, 使得每份的和不大于 x.  
显然如果 x 足够大, 是可以的, 而 x 如果太小则不行, 该题就是要求最小的可行的 x.

# 代码 #

#include <stdio.h>
    
    long a[100000];
    int n, m;
    
    long max(long a, long b) { 
    	return (a > b) ? a : b;
    }
    
    long min(long a, long b) { 
    	return (a < b) ? a : b;
    }
    
    // O(n) 复杂度检验 x 是否能分割数组
    int check(int x) { 
    	int sectionLeft = m;
    	int valueLeft = x;
    	for (int i = 0; i < n; i++) { 
    		if (valueLeft >= a[i]) valueLeft -= a[i];
    		else { 
    			if (!sectionLeft) return 0;
    			sectionLeft--;
    			valueLeft = x - a[i];
    		}
    	}
    	return 1;
    }
    
    int main() { 
    	scanf("%d %d", &n, &m);
    	long from = 0;
    	long to = 0;
    	for (int i = 0; i < n; i++) { 
    		scanf("%ld", a + i);
    		from = max(from, a[i]);
    		to += a[i];
    	}
    	int ans = 0;
    	// 二分查找, 下界是数组元素最大值, 上界是数组元素和
    	while (from <= to) { 
    		int mid = from + (to - from) / 2;
    		if (check(mid)) { 
    			ans = mid;
    			to = mid - 1;
    		} else { 
    			from = mid + 1;
    		}
    	}
    	printf("%d\n", ans);
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 Python查找列表数组N个最大最小元素

找出数组中最大和最小的三个元素： import heapq nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]

墨蓝/ 2023年10月18日 15:42/ 0 赞/ 61 阅读

相关指针指向数组最大和最小元素

利用指针指向数组中的最大和最小元素，即输入数组\{1，2，3，4，5\}，输出5，1。代码如下： include<iostream> using na

Myth丶恋晨/ 2023年02月11日 07:21/ 0 赞/ 16 阅读

相关 1846. 减小和重新排列数组后的最大元素

2021-07-15 LeetCode每日一题链接：[https://leetcode-cn.com/problems/maximum-element-after-de

谁践踏了优雅/ 2023年01月23日 14:52/ 0 赞/ 1 阅读

相关 dp之最大和，m段最大和以及最大子矩阵

前一段时间因为要讲课学习了dp系列算法，学习了很多东西，给大一菜鸟讲了这个系列的算法，当时没有记录，前几天拿起来发现有点忘记了，所以在这里记录一下，最大和系列算法。首先子串

系统管理员/ 2022年09月20日 09:26/ 0 赞/ 154 阅读

相关数组中不相邻元素的最大和

原题链接: [Maximum sum such that no two elements are adjacent][] 题目给定一个只含正数的数组，找到数组满足条件的

今天药忘吃喽~/ 2022年08月09日 11:46/ 0 赞/ 146 阅读

相关循环数组最大子段和

N个整数组成的循环序列a 1 1,a 2 2,a 3 3,…,a n n，求该序列如a i i\+a i\+1 i+1\+…+a j j的连续的子段和的最大值（循环序列是指n个

傷城~/ 2022年06月12日 12:07/ 0 赞/ 199 阅读

相关获取js数组元素的最大值和最小值

var array = [10,2,3,4,5,6,30,8,9]; document.write('max:'); documen

﹏ヽ暗。殇╰゛Y/ 2022年03月28日 06:56/ 0 赞/ 357 阅读

相关数组元素的最大最小值

include<iostream> include<system_error> using namespace std; void M

矫情吗；*/ 2022年03月15日 15:52/ 0 赞/ 348 阅读

相关求数组元素的最大值

package day03; import java.util.Scanner; / 求数组元素的最大值 /

电玩女神/ 2022年02月27日 02:52/ 0 赞/ 301 阅读

相关数组分段使得每个段的元素之和最大的最小

题目描述给 n 个正整数 a\_1 … a\_n, 将 n 个数排成一列后分割成 m 段, 每一段的分数为这段内所有数的和, 该次分割的分数被记为 m 段分数的最大值.

阳光穿透心脏的1/2处/ 2022年02月20日 12:13/ 0 赞/ 191 阅读