算法提高课汇总

算法思路

如果空题段可以确定, 则题意与 AcWing 1089. 烽火传递 基本相同.

而题目求的是最大空题段的最小值, 考虑是否能够用二分求解. 二分的本质是某个属性能够将区间
划分为符合与不符合的连续两段, 显然空题段的长度满足这个性质 — 考虑空梯段若为题目总长$n$,
则$t$任意取值, 随着$n$的减小花费的做题时间增加, 直到大于给定的时间$t$.

具体实现

注意本题与 AcWing 1089. 烽火传递 的细节区别: 本题空出的长度最大为$m$(二分确定的空段长度),
而烽火空出长度最大为$m - 1$ — 连续$m$个烽火台至少一个, 假设位置$x$有一个烽火台, 那么
则最远到$x + m$需要有一个烽火台, 则空出的长度为$x + m - x - 1 = m - 1$.

代码实现

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5e4 + 10, INF = 1e9 + 10;

int n, t;
int w[N];
int f[N], q[N];

bool check(int m)
{
    int hh = 0, tt = -1; q[++ tt] = 0; //为统一计算方式 加入f(0) = 0
    for ( int i = 1; i <= n; i ++ )
    {
        if ( q[hh] < i - m - 1 )    hh ++;
        f[i] = f[q[hh]] + w[i];
        while ( hh <= tt && f[q[tt]] >= f[i] )  tt --;
        q[++ tt] = i;
    }

    int res = INF;
    for ( int i = n - m; i <= n; i ++ ) res = min(res, f[i]);
    return res <= t;
}

int main()
{
    cin >> n >> t;
    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 << l << endl;

    return 0;
}