求蓝桥3539【买二赠一】的题解

Question

题目如图所示，蓝桥官方给出的题解用的贪心算法，但存在bug，例如对于 6 12 23 35 35 50 50这组数据不能得到正确结果，想问问社区里有人能给出正确题解吗

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

问题描述： 给定一个长度为n的整数数组，将其分割成k个连续的子数组使得每个子数组的和最大值最小。求最小值。 输入格式： 第一行两个整数n和k，表示数组长度和分割的子数组个数。 第二行n个整数，表示要分割的数组。 输出格式： 一个整数，表示最小的子数组和的最大值。 示例： 输入： 7 4 3 4 5 6 7 8 9 输出： 9 解析： 将数组分为[3] [4] [5,6] [7,8,9]四部分，每部分元素和为3, 4, 11, 24，最大值为24。不能分成[3,4] [5,6] [7,8] [9]，最大值为20，因为最大值应该最小，因此24为最终答案。 解题思路： 本题是一道二分答案+贪心的题目。 对于二分答案的部分，因为我们要求最小的子数组和的最大值，因此我们可以将答案范围缩小到数组元素和的最大值（设为sum）和数组元素最大值（设为max_num）之间，因为最小值不可能小于max_num，最大值不可能大于sum。 接下来是贪心的部分。我们尝试把数组分成k个连续的子数组。设当前最小的子数组和的最大值为mid，我们就从前到后依次将数组元素加入到当前这个子数组里，直到当前子数组中元素的和超过了mid。此时我们将统计的元素个数加入到已分割出的子数组数量中，并将当前子数组的和清0。最后如果已经分成的子数组个数小于等于k，说明当前的mid可以满足条件，我们可以尝试二分mid的更小的值；否则说明mid太小了，我们需要尝试二分更大的mid。 注意，当数组分割为k个子数组后，最后一个子数组的和并不在mid的分割范围内。因此当我们尝试用当前mid对数组进行分割时，需要判断最后一个子数组的和是否超过了mid的范围，如果超过了，直接退出循环，尝试其它更大的mid。 参考代码：