CF526E

· · 题解

给定环形数组 a_{1\cdots n}，q 次询问给定 k，要求把数组划分成若干和 \leq k 的段，求最小段数。

首先是 $O(qn\log n)$ 的暴力：双指针预处理每个点最远选到哪里，然后倍增。 然后为啥大家都写奇怪需要分析复杂度的做法啊，不如来点更直接的 $O(qn)$。 令上面预处理出来的是 $[i,to_i)$ 是最长合法区间，考虑假设我们钦定 $(n,1)$ 不被跨过会发生什么。只需要从 $x=1$ 开始不断执行 $x\gets to_x$ 直到跨过 $(n,1)$。可是当初始 $x=2$ 时，其最后一段的和不一定满足 $\leq k$，不妨检验最后一段的值加上 $a_1$ 是否仍然 $\leq$，如果可以，前面跳的次数 +1 就可以被贡献到答案；再令 $x=i$ 时不断跳，检验最后一段的和加上 $a_{1\sim i-1}$ 是否 $\leq k$，是的话就能用次数 +1 贡献到答案。可以证明这样能够覆盖到所有情况： - 如果检验成功，那么等价于从 $i$ 出发一直跳 $to_i$，即正确模拟了以 $i$ 为起点的情况。 - 如果检验失败，考虑最后一段不能跳的到 $n$ 为止都 $\leq k$，加上 $a_{1\sim i-1}$ 之后 $>k$ 了，说明这里产生的最后一段至少需要被切为两段，那么从 $n$ 开始往后加到不能加为止，从那个位置的后一个执行贪心能得到不劣的结果。 实际上，钦定的“断边”是任意边都是正确的。