将数组分成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 的可能方法是

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}

和

{[10,5],[3,7} is the optimal one.

它相当于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屋！