二刷提高课，题解目录在这里— 提高课的题解目录

此题目如果没有铺垫还是很有难度的
因为这是在二分的基础上，加上了上题烽火传递的思想
因为从题意可以看出如果我们空的题目足够多（肯定合法）一定满足要求
所以其实是一部分不合法一部分合法（具有二分性）
所以很容易看出二分，但是我们二分出mid后，接下来如何处理？
这里要用到上题的思想，只要最后最小的合法（最长空题数不超过mid）即可
所以这里是在二分的check函数里写单调队列

#include<iostream>
using namespace std;
const int N=5e4+10;
int a[N];
int f[N],q[N];
int n,t;
bool check(int x)
{
    f[0]=0;
    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        while(hh<=tt&&i-q[hh]-1>x)hh++;
        f[i]=a[i]+f[q[hh]];
        while(hh<=tt&&f[q[tt]]>=f[i])tt--;
        q[++tt]=i;
    }
    int res=1e9+10;
    for(int i=n-x;i<=n;i++)res=min(res,f[i]);
    if(res>t)return false;
    else return true;
}
int main()
{
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int l=0,r=5e4+10;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l;
    return 0;
}