石子合并的最低与最高得分策略

"11079可以移动的石子合并" 题目“11079可以移动的石子合并”是一道典型的贪心算法问题，旨在寻找将n堆石子合并成一堆时的最低和最高得分。在这个问题中，每次可以选取至少2堆至多k堆石子进行合并，合并后的新堆石子数即为本次合并的得分。最终的目标是计算出合并过程中的最低得分和最高得分。 首先，我们来分析如何获得最高得分。为了得到最高的合并得分，我们需要每次都合并最大数量的石子。这里，我们可以采取贪心策略，每次合并最大的k堆石子。具体步骤如下： 1. 对所有石子堆按照石子数量降序排列。 2. 按照降序依次选择k堆石子进行合并，直到只剩下一堆石子为止。 3. 将每次合并的石子数累加，得到的就是最高得分。 例如，在示例输入中，当n=7，k=3时，按照上述贪心策略，可以先合并45与22，然后合并67与16，接着合并83与13，再合并96与12，最后合并108与9，这样得到的最高得分就是593。 接下来，我们探讨如何获得最低得分。对于最低得分，我们需要尽可能地减少每次合并的石子总数。贪心策略如下： 1. 对所有石子堆按照石子数量升序排列。 2. 每次选择k堆石子中最小的堆进行合并，直到只剩下一堆石子。 3. 同样，将每次合并的石子数累加，得到的就是最低得分。 然而，这里有一个需要注意的地方。如果n%(k-1)不等于1，那么在最后一轮合并时可能无法恰好合并k堆。在这种情况下，为了确保始终可以进行k堆的合并，我们需要在开始合并前添加若干个包含0个石子的虚拟堆。这样，无论在任何时候，我们都能够选择k堆进行合并，直至合并成一堆。 例如，还是n=7，k=3的情况，我们首先合并5、9和12，然后合并13、16和22，最后合并45、51和26，这样得到的最低得分就是199。 总结一下，解决这个问题的关键在于理解和应用贪心策略。对于最高得分，我们选择最大的k堆合并；对于最低得分，我们选择最小的k堆合并。如果在合并过程中遇到无法刚好合并k堆的情况，可以通过添加虚拟堆来调整。通过这些方法，我们可以有效地计算出石子合并的最低和最高得分。