绿色通道

https://www.acwing.com/problem/content/1092/ 高二数学《绿色通道》总共有 n 道题目要抄，编号 $1,2,\dots ,n$ ，抄第 $i$ 题要花 $a_i$ 分钟。 小 $Y$ 决定只用不超过 $t$ 分钟抄这个，因此必然有空着的题。 每道题要么不写，要么抄完，不能写一半。 下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。 这样应付自然会引起马老师的怙怒，最长的空题段越长，马老师越生气。 现在，小 $Y$ 想知道他在这 $t$ 分钟内写哪些题，才能够尽量减轻马老师的怒火。 由于小$Y$ 很聪明，你只要告诉他最长的空题段至少有多长就可以了，不需输出方案。

输入格式

第一行为两个整数 $n,t$ 。 第二行为 $n$ 个整数，依次为 $a_1,a_2,\dots ,a_n$ 。

输出格式

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

数据范围

$0<n\le 5\times 10^4$ $0<a_i\le 3000$ $0<t\le 10^8$

题解

对于最大值最小问题一般先考虑二分答案。丢瓶盖 有界性： 最长空题段最多时一个都不做, 最小的全做, 即$[0,n]$ 两段性： 最长空题段为 $le{n}_{res}$ 时, 其最小耗时为 $tim{e}_{res}$ 若想空题段长度更小, 需要再做几道题, 即 $le{n}_i<=le{n}_{res}$时, 需满足 $tim{e}_i<=tim{e}_{res}$ 若想空题段长度更大, 需要少做几道题, 即 $le{n}_j>=le{n}_{res}$时, 需满足$tim{e}_j>=tim{e}_{res}$

故证毕, 和丢瓶盖一题很是相似。 接下来就只需要求出空题段不超过$le{n}_{res}$的最小耗时即可。 也就是说, 在任意一个长度为 $le{n}_{res}$ 的区间中, 必须存在一个题被做, 这样问题就转化为烽火传递了。

代码

const int N = 5e5 + 10;
int f[N];
int a[N];
int n, m;
int q[N], hh, tt;
 
bool check(int limit)
{
    hh = 0, tt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (q[hh] < i - limit - 1)
            hh++;
        f[i] = f[q[hh]] + a[i];
        while (hh <= tt && f[q[tt]] >= f[i])
            tt--;
        q[++tt] = i;
    }
    for (int i = n - limit; i <= n; i++)
        if (f[i] <= m)
            return true;
    return false;
}
 
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
 
    int l = -1, r = n + 1;
    while (l != r - 1)
    {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    cout << r << endl;
    return 0;
}