$$\color{Red}{绿色通道【单调队列融合二分（烽火传递plus）】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

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

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

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

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

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

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

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

输入格式

第一行为两个整数 n,t。

第二行为 n 个整数，依次为 a1,a2,…,an。

输出格式

输出一个整数，表示最长的空题段至少有多长。

数据范围

0 < n ≤ 5 × 10 ^ 4

0 < ai ≤ 3000

0 < t ≤ 10 ^ 8

输入样例：

17 11
6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5

输出样例：

3

思考

本题来自于烽火传递和二分的结合我的烽火传递题解

烽火传递的思路

状态转移一定是考虑 i之前的: f[i] = min{f[j]} + w[i], (i - m <= j < i) 【不是 i - m + 1是因为 i还没入队】

为什么这道题区间多了？好像是 m + 1

因为允许出现最大的空白为 m的情况下，相当于每m + 1个区间至少出现一个写的题目，所以其实本质上长度是 m + 1情况下的烽火传递。

只需要把上面的区间向左扩大一格即可。

遍历答案的时候，就不需要考虑未入队，扩大范围的情况，故从i - limit开始寻找答案。

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n, m, N = 50010;
    static int[] q = new int[N];
    static int[] f = new int[N];
    static int[] w = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static boolean check(int limit) {
        int hh = 0, tt = 0;
        for (int i = 1; i <= n; i++) {
            if (hh <= tt && q[hh] < i - limit - 1) hh++;
            f[i] = f[q[hh]] + w[i];
            while(hh <= tt && f[q[tt]] >= f[i]) tt--;
            q[++tt] = i;
        }
        int res = (int) 1e9;
        for (int i = n - limit; i <= n; i++) res = Math.min(res, f[i]);
        return res <= m;
    }

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        String[] s2 = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) w[i] = Integer.parseInt(s2[i - 1]);
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        System.out.println(l);
    }
}