刚抄完历史作业。 首先注意到题目要求最短空题段，所以我们可以联想到经典题目：数列分段。数列分段这道题是使用二分加贪心解决的。 定义 f(x)f(x)f(x) 为每个空题段不超过 xxx 时最少所需的时间。注意到 f(x)f(x)f(x) 是满足单调性的，所以可以二分答案。 现在的问题是如何快速求出 f(x)f(x)f(x)。 贪心显然不行，考虑 DP。 定义 dpi\text{dp}_idpi 为做到第 iii 个题最少所花时间。则有： dpi=min⁡j=i−xi−1dpj+Ai\text{dp}_i=\min_{j={i-x}}^{i-1} \text{dp}_j+A_i dpi =j=i−xmini−1 dpj +Ai 然后就是 f(x)=min⁡j=n−x+1ndpjf(x)=\min_{j=n-x+1}^n \text{dp}_jf(x)=minj=n−x+1n dpj 。 暴力是 O(n2log⁡n)O(n^2\log n)O(n2logn) 的，但显然可以通过线段树优化到 O(nlog⁡2n)O(n\log^2 n)O(nlog2n)。 以下是代码实现。 实现与思路有所差异，例如我的线段树是 1-based 的，所以每个下标都加了 111；还有我偷了点懒，直接将 Ai(i>n)=0A_i(i\gt n)=0Ai (i>n)=0，然后求出 dp2n\text{dp}_{2n}dp2n 。 时间复杂度：O(nlog⁡2n)O(n\log^2 n)O(nlog2n)。