最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

给定一个 正整数 $m$，以及一个长度为 $n$ 的正整数 数组 $w$，其中 $w_i$ 为第 $i$ 个元素的 价值

求一个选择元素的 方案，使得元素的 价值总和 不超过 $m$ 且 相邻元素 的 间距最小

输出该 最小间距

分析

直接做不是很好做，不妨把问题转化为我们熟悉的模型来求解

显然，答案是存在 单调性 的：

1. 任意比 答案 小的 间距 的选择方案，其 元素总和 必然超过 $m$
2. 任意比 答案 大或相等的 间距，必然存在一个方案，使得 元素总和 小于等于 $m$

对于 $2$ 是显然的，我们可以在原合法方案上，删去一些数，从而实现 间距 变大的操作

对于 $1$，我们可以用 反证法：若小于 答案 的 间距 存在符合条件的选元素方案

则我们的 答案 应该是该 间距，这与原答案 矛盾

找出该 单调性，我们就可以上 二分 了

现问题就转化成了：在确定 最小间距 情况下，能否找出选择 元素总和 小于等于 $m$ 的方案

该问题 等价于： 在确定 最小间距 情况下，选择 元素总和 最小的方案 价值 是否 小于等于 $m$

这样本题就变成：AcWing 1089. 烽火传递【单调队列优化DP + 目标状态小优化】

想详细看一下该模型分析的可以看上面的博客，下面我只贴出一部分

状态表示-集合 $f_i$：以 $i$ 为 右端点 的 前缀区间，选择 第 $i$ 个元素的 方案

状态表示-属性 $f_i$：方案选的元素 总贡献最小 $Min$

状态计算 ：

$$\begin{aligned} &f_i = \min\{{ f_j + w_i }\} & (0 \le i - j - 1 \le limit) \\\\ ~ \\\\ \Rightarrow \quad &f_i = w_i + \min\{{f_j}\} & (1 \le i - j \le limit + 1) \end{aligned}$$

Code

时间复杂度： $O(n \log m)$

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

using namespace std;

const int N = 5e4 + 10;

int n, m;
int w[N], que[N], f[N];

bool check(int limit)
{
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        while (hh <= tt && i - que[hh] > limit + 1) hh ++ ;
        f[i] = f[que[hh]] + w[i];
        while (hh <= tt && f[que[tt]] >= f[i]) tt -- ;
        que[ ++ tt] = i;
    }
    if (n + 1 - que[hh] > limit + 1) hh ++ ;  //滑动窗口往后多滑一位
    return f[que[hh]] <= m;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &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\n", r);
    return 0;
}