绿色通道

原题链接

题目描述

高二数学《绿色通道》总共有 n 道题目要抄，编号 \(1,2,…,n\)，抄第 i 题要花 \(a_i\) 分钟。

小 Y 决定只用不超过 t 分钟抄这个，因此必然有空着的题。

每道题要么不写，要么抄完，不能写一半。

下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。

这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。

现在，小 Y 想知道他在这 \(t\) 分钟内写哪些题，才能够尽量减轻马老师的怒火。

由于小 Y 很聪明，你只要告诉他最长的空题段至少有多长就可以了，不需输出方案。

---

思路 二分查找答案+单调队列优化dp

二分证明：

我们假定最终答案为 \(len\)，那么可以发现，对于答案 \(len\)：

• 如果空题段长度小于 \(len\)，那么不能在 \(t\) 时间内达到满足空题长度小于 \(len\) 的条件；
• 如果空题段长度大于 \(len\)，那么在 \(t\) 时间内可以满足空题长度大于 \(len\) 的条件。

上述可得，答案 \(len\) 的二段性得证。我们可以二分答案 \(len\)，找到满足时间小于 \(t\) 的最小 \(len\) 值。

单调队列优化DP

状态定义： \(dp[i]\) 前 \(i\) 个题目中，空题长度最大为 \(len\)，且写第 \(i\) 题的方案集合。

状态属性： 消耗时间的最小值。

状态计算： \(dp[i]=\min\{dp[j]_{(i-len-1\le j\le i-1)}\}+w[i]\)

根据上述dp方程，可以发现与 烽火传递 类似。用单调队列维护区间最值。

Note

对于空题长度 \(len\)，我们可以看成在 \(len+1\) 的长度中，至少有一题需要做完的。

---

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 50010;
const int inf = 0x3f3f3f3f;

int n, t;
int w[N], q[N], dp[N];
// 前 i 个题目中，空题长度最大为 len，且写第 i 题的方案集合。

bool check(int mid) {
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i++) {
        if (q[hh] < i - mid - 1) hh++;
        dp[i] = dp[q[hh]] + w[i];
        while (hh <= tt && dp[q[tt]] >= dp[i]) tt--;
        q[++tt] = i;
    }

    int res = inf;
    for (int i = n - mid; i <= n; i++)
        res = min(res, dp[i]);

    return res <= t;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> t;
    for (int i = 1; i <= n; i++) cin >> w[i];

    int l = 0, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << endl;

    return 0;
}