CCF-CSP第36次认证第四题——跳房子【优化思路：预处理区间最大值】
CCF-CSP第36次认证第四题——跳房子
时间限制： 0.5 秒
空间限制： 512 MiB
相关文件： TUOJ
题目描述
跳房子游戏是西西艾弗岛上孩子们的传统娱乐方式。今天小 P 造访了西西艾弗岛，小 C 向他示范了跳房子游戏该怎么玩。
在地面上有一字排开的 𝑛n 个格子，每个格子上都写着一个数字，第 𝑖i 个格子上写着的数字是 𝑎𝑖ai。这些数字满足 𝑎𝑖<𝑖ai<i 且 𝑎𝑛=0an=0。
一开始，小 C 站在第一个格子上。小 C 是一个擅长跳跃的人，他可以往前跳很远，但为了游戏的趣味性，小 C 规定在第 𝑖i 个格子上最多能往前跳 𝑘𝑖ki 格，而且不能跳到第 𝑛n 个格子后面。也就是说，如果小 C 现在站在第 𝑖i 个格子上，那么他可以跳到第 𝑖+1i+1 个格子和第 min(𝑛,𝑖+𝑘𝑖)min(n,i+ki) 个格子之间的任意格子上。
根据跳房子游戏的规则，如果小 C 在一次跳跃之后落到了第 𝑖i 个格子上，那么他需要后退 𝑎𝑖ai 格，也就是说小 C 在跳跃后会站在第 𝑖−𝑎𝑖i−ai 个格子上。
玩了一会之后，小 P 突然好奇，小 C 最少需要跳多少次才能到达第 𝑛n 个格子呢？小 C 也不知道这个答案，于是他只能来请教你。
输入格式
第一行一个正整数 𝑛n，代表格子的数量。
第二行 𝑛n 个非负整数 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an，其中 𝑎𝑖ai 表示第 𝑖i 个格子上的数字。
第三行 𝑛n 个非负整数 𝑘1,𝑘2,…,𝑘𝑛k1,k2,…,kn，其中 𝑘𝑖ki 表示小 C 在第 𝑖i 个格子时能往前跳的最大格数。
输出格式
输出一行一个整数表示小 C 到达第 𝑛n 个格子需要的最少跳跃次数，如果小 C 不能到达第 𝑛n 个格子输出 -1。
样例1输入
10
0 1 1 1 1 3 1 0 3 0
2 4 5 4 1 4 1 3 5 3
样例1输出
4
样例1解释
从第 11 个格子出发，首先往前跳 22 格到第 33 个格子，然后后退一格，停在第 22 个格子。
从第 22 个格子往前跳 33 个格子到第 55 个格子，后退一格，停在第 44 个格子。
从第 44 个格子往前跳 44 个格子到第 88 个格子，不需要后退，停在第 88 个格子。
从第 88 个格子往前跳两格即到达第 1010 个格子。总共跳跃 44 次。
样例2输入
5
0 1 2 3 0
3 4 4 10 15
样例2输出
-1
子任务
本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。
- 子任务一（3030 分）：保证 𝑛≤1000n≤1000；
- 子任务二（3030 分）：保证 ∀1≤𝑖<𝑗≤𝑛∀1≤i<j≤n 都有 𝑘𝑖≤𝑘𝑗ki≤kj；
- 子任务三（4040 分）：无特殊限制。
对于所有数据，保证 1≤𝑛≤105,0≤𝑎𝑖<𝑖,1≤𝑘𝑖≤1091≤n≤105,0≤ai<i,1≤ki≤109。
提示
本题输入量较大，请采用效率较高的读入方式。
参考题解
该题解时间复杂度可能无法满足题目要求，可看优化
#include<iostream>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
//struct grad {
// int a; //ai表示需要后退的格子数---用pair的first存
// int k; //ki表示最多跳k格---用pair的second存
//} grads[N];
int main () {
int n;
scanf("%d", &n);
PII grads[N];
for(int i = 1; i <= n; i++) scanf("%d", &grads[i].first);
for(int i = 1; i <= n; i++) scanf("%d", &grads[i].second);
//判断不能到达n的情况
//1.每次到n就回退
if(grads[n].first != 0) {
printf("-1\n");
return 0;
}
//2.在某一步陷入循环，不可能有前进的情况
int i = 1;//目前在第几个格子上
int cnt = 0;
while(i < n) {
//求出可以跳到的格子范围 [i + 1, min(n, i + ki)]
int l = i + 1;
int r = min(n, i + grads[i].second);
int res = 0;//存储当前可以跳到的最优选择，即max(i + grads[k + i].second - grads[k + i].first),k为初始值，即从哪开始跳，i表示往后跳了多少格
//从最远的格子往近处遍历
for(int j = r; j >= l; j--) {
res = max(res, j - grads[j].first);
if(grads[j].first == 0)
break; // 最优选项，可以不用再往前遍历
}
if(i == res) { //不可能到底n的第二种情况
printf("-1\n");
return 0;
}
//更新
i = res;
cnt ++; //步数+1
}
printf("%d\n", cnt);
return 0;
}
优化版
优化思路
上述题解采用贪心策略，每次选择当前可跳跃范围内能到达的最远位置，但存在效率问题，最坏情况下时间复杂度高
优化思路：预处理区间最大值——线段树（动态数据）、稀疏表（静态数据，无需更新）
这里是静态数据，所以优先选择稀疏表来优化
稀疏表是一种用于解决静态区间最值查询（RMQ）的高效数据结构。它通过预处理数据，使得每次区间查询的时间复杂度为 O(1)，预处理的时间复杂度为 O(n log n)，空间复杂度为 O(n log n)。
稀疏表的核心思想
-
预处理：对于数组的每个位置
i，计算从i开始、长度为2^j的区间的最值（最大或最小），其中j的取值范围为0 ≤ j ≤ log₂(n)。 -
区间分解：对于任意区间
[L, R]，将其分解为两个长度为2^k的区间（可能有重叠），覆盖整个[L, R]，从而快速合并结果。
优化后
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
// val数组：val[i] = i - a[i]
// 作用：存储跳跃到第i个格子并回退后的最终位置
// 例如：当在第i格跳跃后落到j，由于回退a[j]格，实际最终位置是 j - a[j] = val[j]
int val[N];
// st数组（稀疏表）：st[i][j] 表示从位置i开始，长度为2^j的区间内的最大值
// 作用：预处理区间最大值，实现O(1)复杂度的区间查询
int st[N][20];
// log_table数组：log_table[i] = floor(log2(i))
// 作用：快速计算任意区间长度对应的最大二进制幂次，用于稀疏表查询
int log_table[N];
//构建稀疏表
void build_st(int n) {
// 预处理log_table数组，计算每个数的log2下取整
log_table[1] = 0;
for (int i = 2; i <= n; i++)
log_table[i] = log_table[i/2] + 1; // 递推式：log2(i) = log2(i/2) + 1
// 动态规划构建稀疏表，j表示区间长度的指数（区间长度为2^j）
for (int i = 1; i <= n; i++)
st[i][0] = val[i];
for (int j = 1; (1 << j) <= n; j++) // 确保区间长度不超过n
for (int i = 1; i + (1 << j) - 1 <= n; i++) // 确保区间右端点不超过n
// 合并左右两个子区间的最大值
// 左子区间：[i, i+2^(j-1)-1]，右子区间：[i+2^(j-1), i+2^j-1]
st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
}
// 查询区间[l, r]的最大值
int query_max(int l, int r) {
int k = log_table[r - l + 1]; // 计算区间长度的log2下取整
// 返回两个可能重叠的区间的最大值，这两个区间覆盖整个[l, r]
return max(
st[l][k], // 区间[l, l + 2^k - 1]
st[r - (1 << k) + 1][k] // 区间[r - 2^k + 1, r]
);
}
int main() {
int n;
scanf("%d", &n);
vector<int> a(n + 1), k(n + 1);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) scanf("%d", &k[i]);
// 终点格子必须满足a[n] = 0，否则无法停留
if (a[n] != 0) {
printf("-1\n");
return 0;
}
// 预处理val数组：val[i] = i - a[i]
// 表示跳跃到第i格后的实际位置（考虑回退）
for (int i = 1; i <= n; i++)
val[i] = i - a[i];
// 构建稀疏表，预处理区间最大值
build_st(n);
int pos = 1; // 当前所在格子位置
int cnt = 0; // 跳跃次数计数器
while (pos < n) {
int l = pos + 1; // 可跳跃的最小位置
int r = min(pos + k[pos], n); // 可跳跃的最大位置（不超过n）
// 无有效跳跃区间（无法前进）
if (l > r) {
printf("-1\n");
return 0;
}
// 查询可跳跃区间[l, r]内的最大val值（即最远可达位置）
int max_val = query_max(l, r);
// 如果最大值不超过当前位置，说明陷入循环
if (max_val <= pos) {
printf("-1\n");
return 0;
}
pos = max_val; // 跳跃到最优位置
cnt++; // 增加跳跃次数
}
printf("%d\n", cnt);
return 0;
}总结
对于稀疏表、线段树等数据结构要较为熟练，如果不熟练的话还不如直接用第一个版本，思路更好理解，也能拿一部分分数。但是如果想要追求高分、满分的话，常用的可以优化算法的方法还是要熟练掌握，比如线段树、树状数组、双指针等等。