CF1299C: Water Balance
区间平均化操作;答案是前缀和点集下凸壳的斜率,用单调栈维护分段平均,交叉相乘避免浮点。来源 Codeforces 1299 C · 难度 Codeforces 2100 · 时间 3 s,空间 256 MB · 标签 贪心 / 单调栈 / 凸壳 / 前缀和
题目描述
有 个水箱排成一排,第 个水箱有 升水。一次操作可以选择区间 ,把区间内所有水箱的水量都改成该区间的平均值。
可以进行任意多次操作,求能得到的水量序列中字典序最小的一个。输出每个水箱最终的水量,误差不超过 。
,。
题解
最终最优序列一定单调不降。若存在相邻的 ,只对这两个水箱做一次平均操作, 变小而前面的元素不变,会得到更小的字典序,矛盾。
因此只需考虑由若干连续段组成的答案:每一段内所有水箱取该段原水量的平均值,且各段平均值单调不降。
把前缀和画成点
一段 的平均值就是弦 的斜率。一个分段平均、且段平均值不降的方案,对应从 到 的一条斜率不降的折线。字典序最小的方案正是这些前缀和点的下凸壳;下凸壳的每一段斜率就是对应区间的平均值。
用单调栈在线维护下凸壳。栈中每段记录总和 与长度 ,其平均值为 。加入 后,若栈顶两段的平均值满足
就把它们合并。用交叉相乘判断
避免浮点误差。最终栈中每段展开成 个 。
复杂度
每个段最多入栈、出栈一次,时间为 ,空间为 。
参考
- 题目链接:CF 1299C Water Balance。
- 思路参考:Sshwy Codeforces 笔记。