思路与算法

二分最长允许空题段g，范围为0..n。给定g后，计算在每段连续空题不超过g时，抄题的最小时间，并检查是否不超过t。

在位置0设置已选的虚拟起点，dp[i]表示最后抄了第i题的最小时间。前一题j到i之间有i-j-1道空题，因此转移为dp[i]=a[i]+min(dp[j])，其中max(0,i-g-1)≤j≤i-1。用单调队列在O(n)时间内求所有状态。

结尾还要限制最后一段空题。最后抄题位置应满足j≥n-g，故在max(0,n-g)..n中取最小dp，等价于连接一个免费虚拟终点n+1。若最小时间≤t，则g可行，否则不可行。二分返回最小可行g。

正确性说明

任何抄题方案连同两个虚拟端点，把全部空题分成相邻选中位置之间的若干段。每段至多g题，恰好等价于相邻选中位置距离至多g+1。DP枚举了每个最后抄题位置的所有合法前驱，并以末尾范围检查最后空段，因而求得给定g下的最小抄题时间。

单调队列删去过期候选，并删去费用更高、位置更早而始终不会优于新候选的点，故队首给出的最小值精确，判定正确。

g增大只会放松限制，原可行方案仍可行；g=n允许全部不抄，花费0，一定可行。因此可行性单调，二分找到的第一个可行g就是题目要求的最小最长空段。

复杂度

输入、dp和队列数组初始化O(n)。每次判定重新顺序计算全部状态，每个点入队出队至多一次，需O(n)。整数二分O(log(n+1))次，总时间O(n log(n+1))，空间O(n)，包含初始化；每次重设队列及dp[0]后，后续dp按顺序覆盖，无需重复清空整个数组。

易错点

g个空题对应已抄位置间距g+1，不是g。首段和尾段都要检查；仅约束相邻实际抄题会漏掉边界。g=0表示全抄，预算不足以抄任何题时答案可以是n。新一次判定不能沿用上次的队列候选，必须重新计算。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll budget;
    cin >> n >> budget;
    vector<int> a(n + 1), q(n + 1);
    vector<ll> dp(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    auto feasible = [&](int longest) {
        int head = 0, tail = 1;
        q[0] = 0;
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            while (head < tail && q[head] < i - longest - 1)
                ++head;
            dp[i] = a[i] + dp[q[head]];
            while (head < tail && dp[q[tail - 1]] >= dp[i])
                --tail;
            q[tail++] = i;
        }
        while (head < tail && q[head] < n - longest)
            ++head;
        return dp[q[head]] <= budget;
    };
    int low = 0, high = n;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (feasible(mid))
            high = mid;
        else
            low = mid + 1;
    }
    cout << low << '\n';
}