CodeForces – 1300E Water Balance(贪心)

题目链接:点击查看 题目大意:给出 n 个数字组成的序列,现在可以对数列进行多次操作,每次操作可以选择其中一段连续的数列,用其平均数替换原位置,换句话说,若原连续数列为 1 2 3,则可以替换为 2 2 2,问如何操作可以使得最后答案的字典序最小 题目分析:因为要使得字典序最小,我们可以在线操作,因为涉及到平均数,我们可以将数列分为几个不同的区块,每个区块的平均值都相同,对于每加入的一个新的数字 num ,若当前的 num 比最后一个区块的平均值要小,那么就说明如果将当前这个 num 与最后一个区块合并后,最后一个区块的平均值就会变小,相应的字典序也会变小,当然合并后倒数第二个区块也会受到影响