(color{red}{mathcal{Description}})
跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下：
在地面上确定一个起点，然后在起点右侧画 (n) 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个 格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：
玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。
现在小 RR 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 (d) 。小 RR 希望改进他的机器人，如果他花 (g)个金币改进他的机器人，那么他的机器人灵活性就能增加 (g) ，但是需要注意的是，每次弹跳的距离至少为 (1) 。具体而言，当 (g<d) 时，他的机器人每次可以选择向右弹跳的距离为 (d-g)，(d-g+1)，(d-g+2)，…， (d+g-2)，(d+g-1)，(d+g) ；否则（当 (g geq d) 时），他的机器人每次可以选择向右弹跳的距离为 (1)，(2)，(3)，…，(d+g-2)，(d+g-1)，(d+g) 。
现在小 (R) 希望获得至少 (k) 分，请问他至少要花多少金币来改造他的机器人。
(color{red}{mathcal{Input Format}})
第一行三个正整数 (n) , (d) , (k) ，分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数。相邻两个数之间用一个空格隔开。
接下来 (n) 行，每行两个正整数 (x_i),(s_i),分别表示起点到第 (i) 个格子的距离以及第 (i) 个格子的分数。两个数之间用一个空格隔开。保证 (x_i) 按递增顺序输入。
(color{red}{mathcal{Output Format}})
共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 (k) 分，输出 (-1) 。
(color{red}{mathcal{DataSize Agreement}})
对于全部的数据满足 (1 ≤ n ≤ 500000), (1 ≤ d ≤2000), (1 ≤ x_i, k ≤ 10^9), (|s_i| < 10^5)
(color{red}{mathcal{Solution}})
对于输出 (-1) 的情况，就是所有分数为正数的格子加起来都不能达到 (k) 分
此题的考点就在于选手对二分答案，以及单调队列优化 (dp) 的掌握，二分答案不难想到，在 (check) 时用线性 (dp)，但是这么做只有 (50) 分
在设计状态时，令 (dp[i]) 表示到第 (i) 个格子时能获得的最大分数，则有转移方程如下：
发现只需要转移区间 ([pos[i]-maxd,pos[i]-mind]) 内 (dp[j]) 的最大值即可，所以考虑用单调队列维护此区间内 (dp[j]) 的最大值
代码实现不是特别复杂，注意开 (long long)，以及判断格子能否到达的操作
(color{red}{mathcal{Code}})
#include <bits/stdc++.h>
#define LL long long
#define reg register
using namespace std;
const int kN = 5e5 + 10;
const LL inf = 0x3f3f3f3f3f3f3f3f;
LL dp[kN];
int x[kN], w[kN];
int N, D, K, Ans = -1;
deque< LL > q;
bool ok(int g) {
if (!q.empty()) q.clear();
for (reg int i = 0; i <= N; ++i)
dp[i] = -inf;
int mind = max(1, D - g), maxd = D + g;
int las = 0;
dp[0] = 0LL;
for (reg int i = 1; i <= N; ++i) {
while (x[las] < x[i] - maxd) las++;
while (x[las] <= x[i] - mind && x[las] >= x[i] - maxd && las < i) {
while (!q.empty() && dp[las] >= dp[q.back()]) q.pop_back();
q.push_back(las++);
}
while (!q.empty() && x[q.front()] < x[i] - maxd) q.pop_front();
if (!q.empty())dp[i] = dp[q.front()] + w[i];
if (dp[i] >= K) return true;
}
return false;
}
int main() {
scanf("%d%d%d", &N, &D, &K);
LL ck = 0;
for (reg int i = 1; i <= N; ++i)
scanf("%d%d", &x[i], &w[i]), ck += (w[i] < 0 ? 0 : w[i]);
if (ck < K) return puts("-1"), 0;
int lb = 0, rb = x[N], Mid;
while (lb <= rb) {
Mid = (lb + rb) >> 1;
if (ok(Mid)) Ans = Mid, rb = Mid - 1;
else lb = Mid + 1;
}
printf("%d
", Ans);
return 0;
}
(color{red}{mathcal{Source}})
(NOIp 2017 PJ T4)