8.2 KiB
AcWing 472. 跳房子
一、题目描述
跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下：
在地面上确定一个起点，然后在起点右侧画 n 个格子，这些格子都在同一条直线上。
每个格子内有一个数字（整数），表示到达这个格子能得到的分数。
玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。
第二次再从当前位置继续向右跳，依此类推。
规则规定：玩家每次都必须跳到当前位置右侧的一个格子内。
玩家可以在 任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。
现在小 R 研发了一款弹跳机器人来参加这个游戏。
但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 $d$。
小 R 希望改进他的机器人，如果他花 g 个金币改进他的机器人，那么他的机器人灵活性就能增加 $g$，但是需要注意的是，每次弹跳的距离至少为 $1$。
具体而言，当 g<d 时，他的机器人每次可以选择向右弹跳的距离为 $d−g, d−g+1, d−g+2，…，d+g−2，d+g−1，d+g$；否则（当 g≥d 时），他的机器人每次可以选择向右弹跳的距离为 $1，2，3，…，d+g−2，d+g−1，d+g$。
现在小 R 希望获得 至少 k 分，请问他 至少要花多少金币 来改造他的机器人。
输入格式 第一行三个正整数 $n，d，k$，分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数，相邻两个数之间用一个空格隔开。
接下来 n 行，每行两个正整数 $x_i,s_i$，分别表示起点到第 i 个格子的距离以及第 i 个格子的分数。
两个数之间用一个空格隔开，保证 x_i 按递增顺序输入。
输出格式 共一行，一个整数，表示至少要花多少金币来改造他的机器人。
若无论如何他都无法获得至少 k 分，输出 $−1$。
数据范围
1≤n≤500000,1≤d≤2000,1≤x_i,k≤10^9,|s_i|≤10^5
输入样例：
7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2
输出样例：
2
样例解读
$A$-$G$分别表示$1$号到$7$号格子，红色文字表示该格子对应的分值。
初始状态，当$d = 4$时，无法由起点跳到其它点，此时需要花费$2$金币改造，改造后机器人的移动范围变为$[2,6]$，此时：
- 机器人跳到$A$点，得$6$分，总分$6$分
- 机器人跳到$B$点，得$-3$分，总分$3$分
- 机器人跳到$C$点，得$3$分，总分$6$分
- 机器人跳到$E$点，得$1$分，总分$7$分
- 机器人跳到$F$点，得$6$分，总分$13$分
所以，当花费$2$金币进行改造时，得分不低于$10$分。
二、题目解析
1、想到二分
假设答案为ans,那么必然存在一种跳法，使得可以得到$>=k$的分数,此时的跳跃步数为$[d-ans,d+ans]$。
此时，如果增大ans,那么上面的跳跃区间就会因为$ans$的变大而区间严格变大。
所以，本题可以通过二分来以$log_2n$的复杂度来去掉一维，就是评估一个$g$值，问它是不是可以满足要求。
2、动态规划 + 单调队列优化
假设$f[i]$表示到达$i$号格子时可以获得的最大分值，来思考它是从哪个格子转移过来的：(动态规划)
在给定 $g$个金币的情况下，机器人可以跳$d$这么远，如果现在在$x$个位置上，那么机器人可以跳到距离范围就是
\large [d-g , d+g]
也就是说，距离$i$点距离在$(d-g),(d+g)$之间的所有格子都是可以跳到$i$这个格子上来了,这是一个固定长度的区间，我们需要在这个区间上找出所有的格子，看看哪个格子的$f[x]$最大，就选择从它这个位置上跳到$i$上去，这就是一个前序固定长度区间找最大值问题，想到用滑动窗口求最值问题，使用 单调队列 进行优化。
我们假设可以跳到$i$号格子的前序区间 距离范围 是[j,k],这个范围内的所有点都可能是$f[i]$的前序转移点：
\large f[i]=f[y]+w[i]
那如何确定这个$y$是哪个点呢？就是这个区间里$f[]$最大值的那个嘛~
思路与步骤：
① $DP$+动态规划
② 从左到右去填充$f[i]$统计结果数据表，动态维护一个范围为$[d-g,d+g]$的范围，用$x[i]$与$x[y]$之间的距离差(x[i]>x[y])判断是不是在上面的范围内
三、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
typedef long long LL;
int n, d, k; // n:格子数，d:机器人可以跳的距离,k:想要取得的分值
int x[N], w[N]; // 距离数组x[i]表示i号格子距离出发点的距离，w[i]从i号格子中可以获得的分值
LL f[N]; // f[i]:到达i点时可以获取到的最大分值
int q[N]; // 单调队列,记录的是格子号
bool check(int g) { // g 描述的是给定的金币数量
LL res = 0;
// 多次dp,每次需要清空统计数组
memset(f, -0x3f, sizeof f); // 预求最大，先设最小
f[0] = 0; // 递推起点数据，分值为0,这个要先看状态转移方程，再思考整体初始化、起点初始化
int hh = 0, tt = -1;
// L,R : 左右边界
int L = max(1, d - g), R = d + g;
/*
④ 为什么要先处理入队列，再处理出队列？反过来为什么是错的呢？
答：
*/
for (int i = 1, j = 0, k = 0; i <= n; i++) {
// ① 新元素入队列
while (x[i] - x[k] >= L) { // i走的挺快，k有资格参评了
while (hh <= tt && f[q[tt]] <= f[k]) tt--; // 年龄比k大，值比k小的都去死
q[++tt] = k++; // k入队列
}
// ② 越界元素出队列
while (x[i] - x[j] > R) j++; // j出界,j无法跳到i
while (hh <= tt && q[hh] < j) hh++; // j都出界了，单调队列也需要维护，把比j小的都干掉
// ③ 队列非空,队列头中保存的就是前面[L,R]范围内的分数最大值所对应的y号格子
if (hh <= tt) f[i] = f[q[hh]] + w[i]; // 再加上i号格子中的w[i]分值，就是总分值
// 时刻更新最大值
res = max(res, f[i]);
}
// 因为分值中存在负数，一旦是在半途中出现可以获取到的分值大于等于k时，就可以停止掉，表示已经找到了一个金币数量满足增加了自由度后，可以取得k这样的分值
return res >= k;
}
int main() {
// 加快读入
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> d >> k; // 格子数量，机器人每次可以跳的距离，想要拿到的分数
for (int i = 1; i <= n; i++) cin >> x[i] >> w[i]; // 起点到第i个格子的距离,第i个格子的分数
int L = 0, R = 1e9, ans = -1; // 二分的左右无脑边界值
/*
二分的最后结果有两种方式:
1、使用ans变量记录最终结果，ans初始化为-1,每次找到check()通过的mid,ans=mid,这样，如果最终有答案ans就记录的是答案，否则就记录的是-1。
2、不使用ans变量记录，而是最后再用!check(L)然后输出-1。
个人认为方法1更易理解。
*/
while (L < R) {
int mid = L + R >> 1;
if (check(mid)) {
R = mid;
ans = mid;
} else
L = mid + 1;
}
printf("%d\n", ans);
return 0;
}