将阵列划分为k个邻接分区，使得最大分区的和为最小 [英] Divide array into k contiguos partitions such that sum of maximum partition is minimum

问题描述

这里，最大和子集是给出最大和
的k个子集之一例如：arr = [10,5,3,7]并且k = 2
在k个子集中划分arr的可能方式是{10，[5,3,7]}，{[10,5]，[3,7}，{[10,5,3]，7}和{[10,5]，[3,7]最优的。
编辑：相当于
https://www.codechef.com / DI15R080 / problems / MINMAXTF

Here maximum sum subset is one of k subsets that give maximum sum e.g: arr = [10,5,3,7] and k = 2 possible ways to divide arr in k subsets is {10,[5,3,7]},{[10,5],[3,7},{[10,5,3],7} and {[10,5],[3,7} is the optimal one. it is equivalent of https://www.codechef.com/DI15R080/problems/MINMAXTF

推荐答案

假设您知道答案是 x 意味着最大子集的和等于x 。您可以通过贪婪算法 O（n）验证此假设。 （从左到右遍历数组，并选择项目，直到该子集的总和低于 x ）。现在，您可以在 x 上进行二分查找，并找到 x 的最小值。该算法的复杂性是 O（nlogn）。

Assume you know the answer is x which means sum of the maximum subset is equal to x. You can verify this assumption by a greedy algorithm O(n). (Traverse the array from left to right and pick items until the sum of that subset is lower than x). Now you can binary search on x and find the minimum value for x. The complexity of this algorithm is O(nlogn).

这篇关于将阵列划分为k个邻接分区，使得最大分区的和为最小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！