CF1918D 题解

yyrwlj · 2024-01-31 15:07:08 · 题解

赛后 1 分钟切了。

题意简述

给定一个正整数序列，选择一些点作为分割点，让分割点的和，和分割后每段和的最大值最小。

思路

考虑二分答案。

check 函数考虑动态规划。

设 f_i 表示 i 是分割点的所有满足最大子段和小于等于 mid 的情况下，分割点的最小和。

对原序列构建出前缀和数组 sum，有朴素的转移：

因为原序列都是正整数，所以前缀和的 sum 数组是单调递增的，就可以对 sum_{i-1}-sum_j \le mid 的部分做单调队列优化。

最后只需控制最后一段的和，只要有 sum_n - sum_i \le mid 而且 f_i \le mid 的情况，就说明可以满足 check 的 mid。