根据https://cses.fi/problemset/task/1085
划分数组的最简单方法是从左到右开始，只要你能将当前的数字添加到子集中，并且它不超过最大值(通过二进制搜索它找到这个值)，然后将它添加到当前子集中。否则就开始一个新的子集，然后再做同样的事情
交货。2、4、7、3、5，最大值为8使用上面的方法，你将得到[2,4]，[7]，[3,5]
我知道这个贪心方法是有效的。但问题是你如何证明这一点用数学方法??
，如果我再次发现类似的贪婪相关问题，我是否应该尝试证明它或者它不需要证明每一个贪心问题?
p。抱歉我的语言让人困惑。我希望你能理解我想表达的意思。
这个解决方案有两个部分:二分搜索和贪婪分区。二分查找不是贪婪算法，它依赖于函数的排序值。
对于二分查找，我们知道，如果k部分划分的所有部分可能达到最大和s，我们必须通过拆分具有该最大和的部分之一来达到相同或更低的最大和(当且仅当该部分是唯一保持最大值的部分时，得到的最大值将更低)。
因此，给定输入k，上面s的值是排序的——它们随着k的增加而单调下降，这意味着我们可以对它们进行二分搜索。
关于以目标最大值s进行分区时的贪心积累，我们可以说，如果我们仍然能够加一部分并且保持在s + 1以下，我们保证分区中至少有一部分的和比我们不加值时要小。添加这个值并不能保证我们可以在这个特定的分区尝试中达到目标s和k，但是而不是添加它意味着我们没有尽我们最大的努力使所有的总和尽可能小，这违背了我们的意图。