「APIO 2021」雨林跳跃
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题面描述
在苏门答腊岛的热带雨林中,有 棵树排成一排,从左到右依次用 到 进行编号,其中 号树的高度为 ,且所有树的高度互不相同。 Pak Dengklek 正在训练一只猩猩,让她能够从一棵树上跳到另一棵树上。对于一次跳跃,猩猩可以从一棵树向左或向右跳到比当前这棵树高的第一棵树上。形式化地,如果猩猩当前在 号树,那么当且仅当满足下列条件之一时,她能够跳到 号树上:
- 是满足 的所有 中比 小的最大非负整数;
- 是满足 的所有 中比 大的最小非负整数。
Pak Dengklek 有 个跳跃计划,每个计划用四个整数 和 来描述。对于每个计划,Pak Dengklek 想知道猩猩是否能够从某棵树 出发,经过若干次跳跃,到达某棵树 。若该计划可行,Pak Dengklek 还想知道可行方案中猩猩需要的最少跳跃次数。
实现细节
你需要实现下列函数:
void init(int N, int[] H)
- N:树的数量。
- H:大小为 的数组, 表示 号树的高度。
- 该函数在第一次
minimum_jumps
的调用前,将会被调用恰好一次。
int minimum_jumps(int A, int B, int C, int D)
- :可以用作起点的树的编号范围。
- :可以用作终点的树的编号范围。
- 该函数需要返回可行方案中猩猩需要的最少跳跃次数,或者返回
-1
表示该计划不可行。 - 该函数将被调用恰好 次。
样例
7 3
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2
2
1
-1
考虑如下调用:
init(7, [3, 2, 1, 6, 4, 5, 7])
在初始化完成后,考虑如下调用:
minimum_jumps(4, 4, 6, 6)
该计划意味着猩猩必须从 号树(高度为 )出发,并到达 号树(高度为 )。
一种跳跃次数最少的可行方案为:先跳到 号树(高度为 ),再跳到 号树。
另一种方案为:先跳到 号树(高度为 ),再跳到 号树。
因此,minimum_jumps
应该返回 。
考虑另一个调用:
minimum_jumps(1, 3, 5, 6)
该计划意味着猩猩必须从 号树(高度为 ), 号树(高度为 ),或 号树(高度为 )之一出发,并最终到达 号树(高度为 )或者 6 号树(高度为 )。
唯一种跳跃次数最少的可行方案为:从 号树出发,直接跳到 号树。
因此,minimum_jumps
应该返回 。
再考虑另一个调用:
minimum_jumps(0, 1, 2, 2)
该计划意味着猩猩必须从 号树(高度为 )或者 号树(高度为 )出发,并最终到达 号树(高度为 )。
由于 号树是高度最低的树,所以无法从其他树跳到 号树。
因此,minimum_jumps
应该返回 -1
。
约束
- (对于所有 )
- (对于所有 )
子任务
- (4 分) (for all )
- (8 分) ,
- (13 分) ,
- (12 分)
- (23 分) ,
- (21 分)
- (19 分) 无附加限制
示例测试程序
示例测试程序按如下格式读取输入数据:
- 第 行:
- 第 行:
- 第 () 行: ,表示第 次
minimum_jumps
调用的参数。
示例测试程序按如下格式输出你的答案:
- 第 () 行: 第 次
minimum_jumps
调用的返回值。