python/TangDou/AcWing/MonotonicQueue/1090.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 50010;
const int INF = 0x3f3f3f3f;

int n, m;
int w[N];
int f[N];
int q[N], hh, tt;

bool check(int limit) {
    hh = 0, tt = 0, q[0] = 0;
    for (int i = 1; i <= n; i++) {
        // 窗口的长度是limit
        while (hh <= tt && q[hh] < i - limit - 1) hh++;

        // 直接计算
        f[i] = f[q[hh]] + w[i];

        // i入队列
        while (hh <= tt && f[q[tt]] >= f[i]) tt--;
        q[++tt] = i;
    }
    // 答案可能存在于 n,n-2,...n-m中，枚举一下求最少值即可
    int res = INF;
    for (int i = n - limit; i <= n; i++) res = min(res, f[i]);
    // 最小值比m小的话，那么就是有可行解，我才不管是不是有其它的值也比m小不小！
    return res <= m;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];
    // 二分(求最长的最小),就是碰一下区间的长度，大了就变小，小了就变大
    int l = 0, r = n; // 空段区间长度0~n都有可能
    // 当我们允许的空白时段的长度越长，那么花费的时间越少
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << endl;
    return 0;
}