本文共 1617 字，大约阅读时间需要 5 分钟。
为了解决这个问题，我们需要将N天的花费分成M个连续的组，并使得每个组的总花费尽可能均衡，从而最小化最大的那个组的花费。我们可以使用二分查找来高效地找到这个最小的最大值。
问题分析：我们需要将花费数组分割成M个连续的子数组，使得最大的那个子数组的总和尽可能小。这类似于寻找一个最优的分割点，使得每个分割后的子数组的总花费尽可能接近平均值。
二分查找：我们可以使用二分查找来确定这个最小的最大值。我们设定一个范围，low为数组中的最小值，high为数组总和除以M。然后，我们不断缩小这个范围，直到找到最小的最大值。
检查函数：对于每一个中间值mid，我们需要检查是否存在一种分割方式，使得分割后的每个子数组的总花费都不超过mid，并且恰好分成M组。这个检查可以通过贪心算法来实现。
def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx += 1 M = int(input[idx]) idx += 1 money = [] for _ in range(N): money.append(int(input[idx])) idx += 1 money.sort() low = 0 if money: low = money[0] total = sum(money) high = total // M best = high def can_split(x): if x == 0: return False count = 1 current_sum = 0 for cost in money: if current_sum + cost > x: count += 1 current_sum = cost if count > M: return False else: current_sum += cost if count <= M: return True else: return False while low <= high: mid = (low + high) // 2 if can_split(mid): best = mid high = mid - 1 else: low = mid + 1 print(best)if __name__ == "__main__": main()
通过这种方法，我们可以高效地找到将花费数组分成M个子数组，使得最大的那个子数组的总花费最小的方案。
转载地址：http://kqhfk.baihongyu.com/