C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
//+了一层二分
const int N=50010;
int n,m;
int w[N];
int q[N], f[N];

bool check(int limit){
    int hh=0,tt=0;
    //f[0]=0;可省略
    for(int i=1;i<=n;i++){
        if(q[hh]<i-limit-1)hh++;  //注意这里其实扩宽了区间的长度，真正的区间是limit+1
        f[i] = f[q[hh]]+w[i];
        while(hh<=tt&& f[q[tt]]>=f[i])tt--;
        q[++tt]=i;
    }
    int res=1e9;
    for(int i=n-limit; i<=n; i++) res=min(res, f[i]);

    return res<=m;
}

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;
    }

    printf("%d", r);
    return 0;
}