Binary Block Search 学习笔记

· · 算法·理论

好像是一种新的做法？

暴力算法 1：每一天进行暴力。时间复杂度 O(n)。

暴力算法 2：首先对整周进行暴力，最后对每天进行暴力。时间复杂度 O(\frac{n}{k})。

优化的暴力：首先对每周进行暴力，最后对每天进行暴力。但是

每一周之间可以合并。

所以考虑二进制枚举 i，j=2^i，然后套公式计算 j 周的值，并贪心的选择：能选则选。

最后对每天暴力。时间复杂度 O(\log n)。

同样儒略日那题也可以这样优化暴力。

Code For CF1154C