题解：T561109 【MX-X7-T2】[LSOT-3] 姬誉蛙

rq_hyj · 2025-01-11 16:32:32 · 题解

二分答案竟然只有入门难度？！

做法

先审题

这 k 个子串的最大权值最小可以是多少。

明显的二分答案

二分最大权值最小可以是多少（显然）。check 函数的写法应该有两种，如下：

• 每次 check O(n) 枚举，当 0 的个数乘上 1 的个数大于二分的答案就新开一段（划分一次），最后判断划分次数是否可行即可
• 先跑一遍前缀和，但每次 check 仍有 O(n) 的复杂度，并没有什么大用还增加写代码的难度……