AcWing 1090. 绿色通道

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

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

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

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

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

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

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

输入格式
第一行为两个整数 n,t。

第二行为 n个整数，依次为 a-1,a-2,…,a-n。

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

数据范围
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

#include<bits/stdc++.h>

using namespace std;

const int N = 50010;

int n,m;
int w[N];
int f[N],q[N];//f[i]表示以 i 为右端点，选择第 i 个元素的最小代价

bool check(int k)
{
    f[0]=0;
    int hh=0,tt=0;

    //中间相隔元素不超过 k 个的状态转移：f[i] = min{f[j]} + w[i] (i - k - 1 <= j <= i - 1)

    for(int i=1;i<=n;i++)
    {
        if(q[hh]<i-k-1) hh++; 
        f[i]=f[q[hh]]+w[i]; //f[i] = min{f[j]} + w[i] (i - k - 1 <= j <= i - 1)
        while(hh<=tt&&f[q[tt]]>=f[i]) tt--; //严格单调递增，队头即最小值
        q[++tt]=i;
    }

    for(int i=n-k;i<=n;i++)
        if(f[i]<=m)
            return true;
    return false;
}

int main()
{
    cin>>n>>m;

    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<<r<<endl;

    return 0;
}