参考Macw这题题解的思路 首先我们得出 O(n2)O(n^2)O(n2) 的DP状态转移方程：枚举可以够到的每个点，统计最小值，+1+1+1 就行了. 然后我们注意到枚举的是连续的区间，所以我们可以用线段树来实现区间查找 因为 m≤5×105m\le 5\times 10^5m≤5×105，所以我选择zkw卡常树.（虽然常规线段树、树状数组也不是不行） 这样我们就成功地把时间复杂度降至 O(nlog⁡n)O(n\log n)O(nlogn) 了. 好像用队列做可以降到O(n)？不管了

由于n较小，可以使用广搜，把走过的标记一遍，如果没有路能走了，输-1。 代码如下：

【题目大意】 m个落脚点位于不同位置，超楠要从初始为1的位置跳到n每次只能跳 1∼k1 \sim k1∼k 中的任意值并且要跳到落脚点（或n）题目要求计算最少跳跃次数，如果无法到达则输出 -1。 SUBTASK1: 100% 【算法分析】 本题采用贪心算法 mmm 个落脚点存在数组 1∼n1 \sim n1∼n 中并且同时将起点终点存入数组即数组 000 位置标 111 ， m+1m+1m+1 标记 nnn ，判断是否有两点差距大于k，如果大于k说明无法达到终点输出-1； 我们可以用一个标记记录超楠此时所在位置，循环向下扫描直到扫描到 aia_iai 与超楠所在位置距离大于 kkk 时，超楠就需要跳到 ai−1a_{i-1}ai−1 的位置，并记录超楠跳跃次数，注意最后超楠可能并没有跳到 nnn 所以我们要判断跳跃次数加 111 。 时间复杂度 O(n) 。 【参考代码】