最近在补全提高课所有题目的题解,宣传一下汇总的地方提高课题解补全计划
题目描述
给定一个 正整数 $m$,以及一个长度为 $n$ 的正整数 数组 $w$,其中 $w_i$ 为第 $i$ 个元素的 价值
求一个选择元素的 方案,使得元素的 价值总和 不超过 $m$ 且 相邻元素 的 间距最小
输出该 最小间距
分析
直接做不是很好做,不妨把问题转化为我们熟悉的模型来求解
显然,答案是存在 单调性 的:
- 任意比 答案 小的 间距 的选择方案,其 元素总和 必然超过 $m$
- 任意比 答案 大或相等的 间距,必然存在一个方案,使得 元素总和 小于等于 $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;
}
吗
不因该是o(nlog(n))
感觉每一步不是最小间距而是最大间距(或间距的上界),因为每一步中j是在i左边长度最大为limit的窗口内滑动的。
当然,二分是为了找到总体的最小间距。
if (n + 1 - que[hh] > limit + 1) hh ++ ; //滑动窗口往后多滑一位
这是什么意思呢?看不懂
在烽火传递那篇题解里有讲过,可以去看一下QwQ