思路

二分查找&单调队列优化DP

c++

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

const int N=50005;
int n, m;
int w[N], f[N];
deque<int> q;

int main(){
    memset(f, 0x00, sizeof f);
    cin>>n>>m;
    for(int i=1; i<=n; ++i) cin>>w[i];

    function<bool(int)> check=[](int limit){
        q.clear();
        q.push_back(0);
        for(int i=1; i<=n; ++i){
            if(q.front()<i-limit-1) q.pop_front();
            f[i]=f[q.front()]+w[i];
            while(!q.empty() && f[q.back()]>=f[i]) q.pop_back();
            q.push_back(i);
        }
        for(int i=n-limit; i<=n; ++i)
            if(f[i]<=m) return true;
        return false;
    };

    int l=0, r=n;
    while(l<r){
        int mid=l+(r-l)/2;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;

    return 0;
}

python

from typing import List
class Solution:
    def main(self, n:int, m:int, a:List[int]):
        f=[0 for _ in range(n+1)]

        def check(limit):
            q=[0]
            for i in range(1, n+1):
                if q[0]<i-limit-1: q.pop(0)
                f[i]=f[q[0]]+a[i-1]
                while q and f[q[-1]]>=f[i]: q.pop(-1)
                q.append(i)
            for i in range(n-limit, n+1):
                if f[i]<=m: return True
            return False

        l, r=0, n
        while l<r:
            mid=l+(r-l)//2
            if check(mid): r=mid
            else: l=mid+1
        print(r)

if __name__ == '__main__':
    n, m=map(int, input().split())
    a=list(map(int, input().split()))
    sol=Solution()
    sol.main(n, m, a)