Skip to content

「NOIP2017」跳房子

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

跳房子,也叫跳飞机,是一种世界性的儿童游戏,也是中国民间传统的体育游戏之一。

跳房子的游戏规则如下:

在地面上确定一个起点,然后在起点右侧画 nn 个格子,这些格子都在同一条直线上。每个格子内有一个数字(整数),表示到达这个 格子能得到的分数。玩家第一次从起点开始向右跳,跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳,依此类推。规则规定:

玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏,获得的分数为曾经到达过的格子中的数字之和。

现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷,它每次向右弹跳的距离只能为固定的 dd。小 R 希望改进他的机器人,如果他花 gg 个金币改进他的机器人,那么他的机器人灵活性就能增加 gg,但是需要注意的是,每 次弹跳的距离至少为 11。具体而言,当 g<dg < d 时,他的机器人每次可以选择向右弹跳的距离为 dg,dg+1,dg+2,,d+g1,d+gd - g, d - g + 1, d - g + 2, \ldots, d + g - 1, d + g;否则当 gdg \geq d 时,他的机器人每次可以选择向右弹跳的距离为 1,2,3,,d+g1,d+g1, 2, 3, \ldots, d + g - 1, d + g

现在小 R 希望获得至少 kk 分,请问他至少要花多少金币来改造他的机器人。

#输入格式

第一行三个正整数 n,d,kn, d, k ,分别表示格子的数目,改进前机器人弹跳的固定距离,以及希望至少获得的分数。相邻两个数 之间用一个空格隔开。

接下来 nn 行,每行两个整数 xi,six_i, s_i ,分别表示起点到第 ii 个格子的距离以及第 ii 个格子的分数。两个数之间用一个空格隔开。保证 xix_i 按递增顺序输入。

#输出格式

共一行,一个整数,表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 kk 分,输出 1-1

#输入输出样例

样例输入 #1

7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

样例输出 #1

2

样例解释 #1

花费 22 个金币改进后,小 R 的机器人依次选择的向右弹跳的距离分别为 2,3,5,3,4,32, 3, 5, 3, 4, 3,先后到达的位置分别为 2,5,10,13,17,202, 5, 10, 13, 17, 20,对应 1,2,3,5,6,71, 2, 3, 5, 6, 766 个格子。这些格子中的数字之和 1515 即为小 R 获得的分数。

样例输入 #2

7 4 20
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

样例输出 #2

-1

样例解释 #2

由于样例中 77 个格子组合的最大可能数字之和只有 1818,所以无论如何都无法获得 2020 分。

#数据范围与约定

本题共 10 组测试数据,每组数据等分。

对于全部的数据满足 1n5×1051 \le n \le 5 \times 10^51d2×1031 \le d \le 2 \times 10^31xi,k1091 \le x_i, k \le 10^9si<105|s_i| < 10^5

  • 对于第 1,21, 2 组测试数据,保证 n10n\le 10
  • 对于第 3,4,53, 4, 5 组测试数据,保证 n500n \le 500
  • 对于第 6,7,86, 7, 8 组测试数据,保证 d=1d = 1

#思路

显然 gg 的取值可以通过二分的方法得出,因为当花费 gg 枚金币可以得到至少 kk 分时,花费 g+1g + 1 枚也可以得到至少 kk 分。

fif_i 表示跳到第 ii 格时获得的最大分数,显然可以朴素地进行转移:

1
2
3
4
5
6
for (int j = 0; j < i; j++) {
// 如果能从点 j 跳跃到点 i 就更新 f[i]
if (l <= x[i] - x[j] && x[i] - x[j] <= r) {
f[i] = std::max(f[i], f[j] + s[i]);
}
}

这样的时间复杂度为 O(n2logn)O(n^2 \log n),只能拿到 5050 分。

由于题目中保证了 xix_i 按递增顺序输入,那么在第二重循环时倒序枚举,如果遇到第一个无法从点 jj 跳跃到点 ii 的点,那么直接跳出循环即可。

1
2
3
4
5
6
7
for (int j = i - 1; j >= 0; j--) {
if (l <= x[i] - x[j] && x[i] - x[j] <= r) {
f[i] = std::max(f[i], f[j] + s[i]);
} else if (x[i] - x[j] > r) {
break;
}
}

这样就可以拿到 8080 分了。

继续往下想,当 gg 为定值时,随着 ii 的增加,break 时的 jj 的值只会越来越大而不会变小,因此可以用单调队列来维护,就能通过所有的测试点了。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
#include <utility>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5e5 + 5;
const long long INF = 0x3f3f3f3f3f3f3f3f;

int n, d;
long long k, f[N], sum;
std::pair<long long, long long> a[N];

bool check(long long l, long long r) {
for (int i = 1; i <= n; i++) {
f[i] = -INF;

for (int j = 0; j < i; j++) {
if (l <= a[i].first - a[j].first && a[i].first - a[j].first <= r) {
f[i] = std::max(f[i], f[j] + a[i].second);
}
}

if (f[i] >= k) return true;
}

return false;
}

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> d >> k;

for (int i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;

sum += a[i].second;
}

long long l = 0, r = INF;

while (l < r) {
long long mid = l + r >> 1;

if (check(std::max(d - mid, 0ll), d + mid)) {
r = mid;
} else {
l = mid + 1;
}
}

cout << (r == INF ? -1 : r) << endl;

return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <algorithm>
#include <utility>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5e5 + 5;
const long long INF = 0x3f3f3f3f3f3f3f3f;

int n, d;
long long k, f[N], sum;
std::pair<long long, long long> a[N];

bool check(long long l, long long r) {
for (int i = 1; i <= n; i++) {
f[i] = -INF;

for (int j = i - 1; ~j; j--) {
if (l <= a[i].first - a[j].first && a[i].first - a[j].first <= r) {
f[i] = std::max(f[i], f[j] + a[i].second);
} else if (a[i].first - a[j].first > r) {
break;
}
}

if (f[i] >= k) return true;
}

return false;
}

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> d >> k;

for (int i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;

sum += a[i].second;
}

long long l = 0, r = INF;

while (l < r) {
long long mid = l + r >> 1;

if (check(std::max(d - mid, 0ll), d + mid)) {
r = mid;
} else {
l = mid + 1;
}
}

cout << (r == INF ? -1 : r) << endl;

return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <algorithm>
#include <deque>
#include <utility>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5e5 + 5;
const long long INF = 0x3f3f3f3f3f3f3f3f;

int n, d;
long long k, f[N], sum;
std::pair<long long, long long> a[N];

bool check(long long l, long long r) {
std::deque<long long> q;

for (int i = 1, j = 0; i <= n; i++) {
f[i] = -INF;

while (j < i && l <= a[i].first - a[j].first) {
if (f[j] != -INF) {
while (!q.empty() && f[q.back()] <= f[j]) q.pop_back();
q.push_back(j);
}

j++;
}

while (!q.empty() && a[i].first - a[q.front()].first > r) {
q.pop_front();
}

if (!q.empty()) {
f[i] = std::max(f[i], f[q.front()] + a[i].second);
}

if (f[i] >= k) return true;
}

return false;
}

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> d >> k;

for (int i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;

sum += a[i].second;
}

long long l = 0, r = INF;

while (l < r) {
long long mid = l + r >> 1;

if (check(std::max(d - mid, 0ll), d + mid)) {
r = mid;
} else {
l = mid + 1;
}
}

cout << (r == INF ? -1 : r) << endl;

return 0;
}