线上OJ：
一本通：http://ybt.ssoier.cn:8088/problem_show.php?pid=1417\
核心思想
首先、本题中提到 “ 至少 要花多少金币改造机器人，能获得 至少 k分 ”。看到这样的话语，基本可以考虑要使用 二分答案。
那么，本题中的 答案 是什么？就是: 在确定维修金币g的情况下，能获得的分数是否会＞ k 。
由于本题中的 格子在同一条直线上，且只能从左往右跳，所以 每一种答案 都可以使用 动态规划 来解决。
而且动态规划的 dp 方程也很好找，因为 当前格子的最高分 肯定是由 之前某个最高分的格子跳过来的，即：
d p [ i ] = m a x ( d p [ i ] , d p [ j ] + a [ i ] ) dp[i] = max(dp[i], dp[j] + a[i]) dp[i]=max(dp[i],dp[j]+a[i])
所以，我们从 i 号格子前面的第一个格子开始查找得分最高的格子。在这里需要注意的是：不是所有的 j 都需要查找。只有当 j 的跳跃区间 [d-g, d+g] 能够触达（或包含）i坐标 的时候，这个 j 才能用于更新dp[i]。
以下三个举例（及配图）便于理解j和i的关系
举例1： i 号格子位于坐标10，j 号格子位于坐标5（此时 j 的跳跃区间为 [2,4]，也就是 j 能跳到的地方为[7,9]），所以此时 j 号格子无法触达 i，所以 j 号格子不需要用于更新dp[i]。
举例2： i 号格子位于坐标10，j 号格子位于坐标5（此时 j 的跳跃区间为 [2,6]，也就是 j 能跳到的地方为[7,11]），所以此时 j 号格子可以触达 i，所以 j 号格子需要用于更新dp[i]。
举例3： i 号格子位于坐标10，j 号格子位于坐标5（此时 j 的跳跃区间为 [6,8]，也就是 j 能跳到的地方为[11,13]），所以此时 j 号格子无法触达 i，所以 j 号格子不需要用于更新dp[i]。
综上所述，有效的 j 点应该满足
d
−
g
<
=
x
[
i
]
−
x
[
j
]
<
=
d
+
g
d-g < = x[i] - x[j] < = d+g
d−g<=x[i]−x[j]<=d+g，
我们令左边界为 l = d - g，右边界为 r = d + g，则仅当 满足①和②式的 j 点 才参与dp[i]的运算
x
[
i
]
−
x
[
j
]
>
=
l
x[i] - x[j] > = l
x[i]−x[j]>=l； ①
$x[i] - x[j] < =r $； ②
题解代码：
解法一：二分答案 + 动态规划（仅80%分数）
#include <bits/stdc++.h>
#define ll long long
#define MAXN 500005
using namespace std;
int n, d, k;
ll x[MAXN], s[MAXN], dp[MAXN];
// 检查花费g个金币进行改造后，最高得分是否会超过 k
bool check(int g)
{
// 计算在花费g金币下，机器人每次向右跳的距离边界[l, r] = [d-g, d+g]。注：左边界不能小于1
int l = max(1, d - g); // 机器人每次能跳跃的最小距离
int r = d + g; // 机器人每次能跳跃的最大距离
memset(dp, 0xaf, sizeof(dp)); // 全部初始化为一个很小的数。
dp[0] = 0; // 数据即分数都从第一个格子开始，所以第0个格子初始化为0分
for(int i = 1; i <= n; i ++)
{
// 从i的前一个格子开始枚举j，直到j枚举到起点（如果i和j之间的距离已经超过弹跳上限r，则没必要继续j--了）
for(int j = i - 1; (j >= 0) && (x[i] - x[j] <= r); j --)
{
// 如果j号格子距离i号格子不能太近，至少要≥机器人弹跳的最小距离”,否则就j--，寻找更远的j
if(x[i] - x[j] >= l)
{
// i的最高得分应该是从前面能跳过来的格子j里得分最高的格子跳过来的
dp[i] = max(dp[i], dp[j] + s[i]);
if(dp[i] >= k) return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d%d", &n, &d, &k);
for(int i = 1; i <= n; i ++)
scanf("%lld%lld", &x[i], &s[i]);
// 由于x[i]的坐标范围可到 10^9，在极端情况下有可能前面全是负值，只有最后一个x[n]是正值，此时要搜索的答案g也会达到 10^9（即一步跳到最后一个正值）。所以二分答案时 r 应取到 x[n]。但如此一来，效率就变低了，只能拿到80%的分数
int l = 0, r = x[n], mid, ans = -1;
while(l <= r)
{
mid = (l + r) >> 1;
if(check(mid))
{
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << ans << endl;
return 0;
}
以上方法只能拿到80分，因为二分答案的右区间 r 取值为 x[n]，数据过于庞大。
解法二、二分答案 + 动态规划 + 单调队列（100%）
由于 二分答案时的 r 取值为 x[n]过于庞大，所以此时考虑对 check 函数进行优化。由于 dp[i] 是之前的某个最大值 dp[j] 跳过来,所以可以考虑优先队列；同时由于 j 是有区间的，所以考虑优先队列的升级版–单调队列（单调队列适合在一个动态小区间中寻找极值）
#include <bits/stdc++.h>
#define ll long long
#define MAXN 500005
using namespace std;
int n, d, k;
ll x[MAXN], s[MAXN], dp[MAXN];
//检查花费g个金币进行改造后，最高得分是否会超过k
bool check(int g)
{
// 计算在花费g金币下，机器人每次向右跳的距离边界[l, r] = [d-g, d+g]。注：左边界不能小于1
ll l = max(1, d - g); // 机器人每次向右跳的最小距离
ll r = d + g; // 机器人每次向右跳的最大距离
memset(dp, 0xaf, sizeof(dp));
dp[0] = 0; // 数据即分数都从第一个格子开始，所以第0个格子初始化为0分
ll j = 0;
deque<int> q;
for(int i = 1;i <= n;i ++)
{
// 根据区间[l, r]，剔除队尾的
while(x[i] - x[j] >= l) // 根据i查找所有符合跳跃左边界的j
{
// 将队列中比 dp[j] 还小的直接移除 (由于按照单调队列存储，故从队尾判断)
while( !q.empty() && dp[q.back()] < dp[j] )
q.pop_back();
q.push_back(j); // 把 j 放到单调队列的尾部，此时dp[j]是当前区间内最小的
j ++;
}
// 根据区间 [l, r]，剔除队头的
while(!q.empty() && x[q.front()] + r < x[i]) // 如果最大的格子距离i太远，已经超过弹跳上限r
q.pop_front(); // 则说对对头元素不在 [l,r] 内，弹出
if(!q.empty()) // 如果此时队列依然非空，则取队首的元素下标 q.front() 来做 dp
dp[i] = dp[q.front()] + s[i];
if(dp[i] >= k)
return true;
}
return false;
}
int main()
{
scanf("%d%d%d", &n, &d, &k);
for(int i = 1; i <= n; i ++)
scanf("%lld%lld", &x[i], &s[i]);
int l = 0, r = x[n], mid, ans = -1;
while(l <= r)
{
mid = (l + r) >> 1;
if(check(mid))
{
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << ans << endl;
return 0;
}
备注：这道题想 混分 有点 难，虽然参考输入样例2中给出了输出 -1 的场景（即：所有正的分数总和依然达不到目标分数k），但是实际的测试数据中并没有这种情况，所以这道题骗分骗不到。
