第174场双周赛Q1题号100960题目叫“最好可到达的塔”。我第一眼看到这个标题脑子里已经把解法猜了个七七八八这题十有八九是“跳跃游戏”的变体——给你一堆塔从起点塔出发每座塔有各自的跳跃能力能跳到的塔就算可到达最后在可到达的塔里选一个“最好”的通常是高度最高的。Q1的定位决定了它不会太复杂核心考察点就两个怎么判断一个塔能不能到怎么在“能到”的集合里快速找最优。说实话这题的难度不在于算法本身有多深而在于很多人一上来就想复杂又是BFS又是DP最后写出一堆代码还超时。实际上这类“可达最优”的题目只要抓住“可达集合的连续性”这个性质一句话就能讲清楚解法。我按尚未拿到完整题面时的常见设定来还原思路你拿到的版本就算细节有出入比如跳跃力换成能量值核心方法一样适用。适合谁看如果你是刚开始打周赛的新手这篇能帮你建立“贪心扫描”的直觉如果是老手重点看后面边界处理和实战节奏的部分。1. 读懂“最好可到达的塔”三个关键词就是解题线索1.1 “塔”到底是什么从竞赛出题习惯来看“塔”就是一维数组里的元素。每座塔有两个关键属性一个是它自身的价值题目叫“最好”多半指高度、收益、分数这类可以比较大小的数值另一个是它的“跳跃能力”也就是从这座塔出发能向前跳多远。你从第0座塔起步跳着跳着就能到达一部分塔剩下那些超过跳跃范围的塔看着再高也跟你没关系。可能有人会问为什么不是二维坐标里的塔因为Q1的定位决定了数据结构和算法不能太复杂二维可达性问题动辄就是BFS加优先队列那是Q3、Q4的强度。一维数组加跳跃约束才是双周赛第一题的正确姿势。所以我下面所有讨论都以“塔排成一排下标从0开始”为前提。做这种题第一步不是写代码而是确认数据结构形态。很多新手看到“塔”字就脑补出平面地图然后开始建图、跑搜索直接把简单题做复杂了。我自己的习惯是先看输入描述里是“数组”“下标”还是“坐标”“网格”后者才需要考虑二维情况。数组类的“塔”先按一维区间问题处理Q1基本不会翻车。1.2 “可到达”的本质是区间而不是散点这是整道题最关键的性质。假设你站在塔i它最多能跳jump[i]步那么从i出发塔i1、i2、……、ijump[i]全都能直接到达。中间不存在“跳过一两个塔”的情况因为距离更短的跳跃一定也合法。这样一来所有能到达的塔连在一起一定是一个从0开始的连续区间。这个性质太重要了它直接决定了解法的复杂度。如果可达集合是散点你就必须老老实实BFS或者DP如果是连续区间那就只需要维护一个“能到达的最右边界”扫一遍数组完事。很多人卡在这题就是因为没想通“连续”这个点。我举个具体的例子塔0的跳跃能力是3那么塔1、塔2、塔3都直接可达。哪怕塔2的高度特别高你也不需要考虑“绕路”的问题因为从塔0直接一步就跳过去了。连续性的本质是“近处一定比远处更容易到达”这在单向、无消耗跳跃模型里永远成立。想通这一点后面所有代码都顺理成章。1.3 题目大概率的长相题面还原根据标题和Q1的定位原题大概率是下面这个形式我按最常见设定还原一下有n座塔排成一排下标从0到n-1。第i座塔的高度为h[i]最大跳跃距离为jump[i]。你初始在第0座塔从塔i可以跳到任意塔ji j i jump[i]。求所有可到达的塔中高度最高的塔的下标或高度。如果题目细节和我还原的不完全一样比如不是jump数组而是从起点给一个固定能量k、每跳一步消耗1那么只要把jump[i]换成固定的k即可贪心写法完全不变。这就是我说“细节有出入不影响思路”的原因。还有一个可能的变化是塔的高度本身充当跳跃能力比如能跳h[i]步那代码里连jump数组都省了直接用h[i]就行。但无论怎么变核心都是“从当前可达区间的最右端不断向外扩展”这个模型是稳定的。2. 思路演进从暴力BFS到一行贪心2.1 暴力BFS为什么能过但没必要最朴素的想法是建图每个点i向右连jump[i]条边然后从0出发BFS把所有能到的点标记出来最后遍历一遍找最高。正确性没问题但复杂度是O(n * max(jump))。如果n是10^5jump[i]平均也是10^5量级连边和遍历的规模就是10^10比赛环境必炸。就算用邻接表省掉连边BFS访问到的边数还是那么多。所以在Q1这个位置出题人摆明了想让你找线性做法。有同学可能会想Q1的数据范围会不会很小暴力能过这种侥幸心理要不得。双周赛第一题虽然简单但数据范围通常是1e5甚至2e5目的就是卡掉所有非线性的做法。你在比赛里赌数据弱不如直接想最优解反正贪心也就多花两分钟思考。2.2 用DP能不能做DP的思路也自然定义dp[i]表示塔i是否可达转移时看前面i-k到i-1范围内有没有可达的塔。写成代码就是内层循环扫窗口复杂度还是O(nk)跟BFS一个量级。但如果用“窗口内是否存在可达点”这个视角你会发现只需要维护一个变量到目前为止能到达的最右下标far。只要i far塔i就是可达的因为远方的塔都可达近处的塔不可能不可达。这就是把DP的窗口优化成了贪心。我见过有人写了一个“看起来很聪明”的DPdp[i]表示从0到i能否到达转移用前缀和优化把复杂度降到O(n)。这当然能AC但比贪心多花了三倍代码量。竞赛里Q1要的是最短时间AC能用O(n)O(1)空间的贪心就没必要写O(n)O(n)空间的DP。当然如果你一开始没想到贪心能用前缀和优化DP修正TLE也是一种本事至少比卡死强。2.3 贪心的正确性证明来严格说下为什么一个far就够了。定义far为当前已确认可达的塔的最大下标。初始far0。遍历i从0到n-1如果i far说明从前面所有可达点出发都够不到i而且由于可达下标是连续的i之后的所有塔也全都不可达直接break。如果i far塔i必然可达。此时更新far max(far, i jump[i])因为从i出发能覆盖到ijump[i]。这个更新过程其实就是在不断扩大“连续可达区间”的右端点。由于每个点最多被扫到一次整体O(n)。证明里最关键的一步是连续性一旦从某个可达点p能跳到q则p到q之间的所有点都可由p直接跳到因此不可能出现“中间有洞”的可达集合。建议你自己在纸上画几个例子把这条性质写清楚考试时就不虚。这个证明比经典跳跃游戏还简单因为跳跃游戏里每个点的跳跃能力不同而这里如果全体塔的jump都相同那far就是ik不断推进。即使jump不同连续性依然成立因为这跟“每个点能跳多远”无关只跟“距离更近一定可以跳”有关。想通这一层你就再也不会怀疑贪心漏解了。2.4 从“判断可达”到“顺便求最好”判断完可达求“最好”就简单了在遍历过程中只要i可达就把它跟当前最优高度比较更新答案。这里有个编码顺序的讲究必须先判断i far再更新答案最后扩展far。反过来写可能会在i不可达时错误地更新答案虽然最后答案不一定错但逻辑会乱调试时容易怀疑人生。我把这个顺序总结成三个短语先问“到没到”再比“谁更好”最后“往外扩”。下一次遇到类似题目直接套能省不少脑力。还有个小细节起点塔一定可达所以答案初始化为第0座塔的高度和编号。千万别把best_h初始化为0否则遇到负高度数据虽然这题一般不会或者所有塔都不可达的情况会返回一个不存在的答案。3. 代码实现三分钟写出AC版本3.1 Python写法与逐行解释def best_reachable_tower(h, jump): n len(h) far 0 best_h h[0] best_idx 0 for i in range(n): if i far: break if h[i] best_h: best_h h[i] best_idx i far max(far, i jump[i]) return best_idxfar初始0代表第0座塔一定可达。best_h和best_idx初始化为第0座塔的信息因为起点也算可到达的塔如果后续没有更高的答案就是它。循环里先判断i是否还落在可达区间内再比较高度最后用当前塔的跳跃能力扩大边界。返回下标。如果题目要求1-based输出前1。Python版本要注意的点是如果h是空数组代码会崩但竞赛题n至少为1。另外如果h[i]可能相等而你被要求返回编号最大的那个就把比较从h[i] best_h改成h[i] best_h这样后出现的相等高度会覆盖之前的答案。这个细节看题面别惯性写成严格大于。3.2 C写法与类型细节int bestReachableTower(vectorint h, vectorint jump) { int n (int)h.size(); int far 0; int bestH h[0], bestIdx 0; for (int i 0; i n; i) { if (i far) break; if (h[i] bestH) { bestH h[i]; bestIdx i; } far max(far, i jump[i]); } return bestIdx; }C这边唯一要注意的是i jump[i]可能超过int表示范围虽然这题一般不会但遇到变体题jump[i]给到1e9时建议把far和i都用long long。另外vector传引用避免拷贝尤其当n是2e5时传值拷贝会白白增加O(n)开销虽然对于这题不至于TLE但养成好习惯没坏处。在代码风格上我建议把输出格式提前确认好。题目如果问“最高的塔的高度”那返回best_h如果问“最高的塔的编号”返回best_idx如果问“从0到该塔需要跳几步”那这题就变成另一个问题了。Q1一般只问高度或编号不会问步数但读题时别跳着看。3.3 边界情况对照表场景期望行为n1只有起点塔返回它的下标0jump[0]0只能停留在起点后面全部不可达最高塔落在断裂点之后不能选它答案应该是断裂前最高塔多座塔等高按题意取编号最小或最大严格大于区分起点塔本身就是最高的返回0不要漏掉初始化答案这些边界我在比赛时几乎每次都踩一遍尤其是n1和jump全0的情况。很多同学的代码在这些数据上不是越界就是答案错误本质上都是没把“起点塔必达”这个前提想明白。偷懒的办法是提交前先自己在脑子里跑一遍最小数据n1的时候循环只执行一次far不变答案是0这样就稳了。4. 竞赛实战从读题到AC的完整节奏4.1 读题阶段提取什么双周赛第一题的目标不是“做出来”而是“快速做出来”给后面难题留时间。读题时我用十秒圈出三样东西起始条件从哪出发、移动规则怎么算可达、目标函数比高度还是比编号。题目里只要出现“最远能跳几步”“能到达的塔”“最高/最好”这类词基本就是跳跃游戏变体解法直接锁定贪心。这里有个经验之谈Q1的题面一般都很短但越短越要逐字读。我曾经因为漏看“高度相同返回编号较大”这句话多交了两发WA。比赛界面没有编译器提示WA一次就是五分钟惩罚对心态的打击比分数还大。所以读题宁可慢十秒也不要因为粗心多花五分钟。4.2 手搓样例与极端数据验证写完代码先别急着提交在本地随手造几组数据试全0跳跃能力far永远是0循环在i1时break答案起点。跳跃能力递增所有塔可达答案最高塔。断裂点靠前最高塔在断点后验证不会被选到。最高塔在起点验证初始化逻辑正确。这组验证30秒做完能规避八成提交错误。尤其是“断裂点靠前”这个数据能直接看出你的break逻辑有没有写对。如果你发现答案选到了断点后面的塔那一定是在i far时没有break或者是用不可达的i更新了far。这种低级错误在紧张状态下特别容易犯本地跑一下就能抓出来。4.3 现场翻车最常见的三种姿势一是写了DP但是内层循环给了k一测大数据直接TLE然后才想起来有贪心二是输出高度而不是下标或者反过来白白吃一发WA三是“相等高度时输出编号最大”没注意到被题目细节坑。这些都是可以靠读题规避的低级失误。我自己的现场策略是看到这题类型后先花30秒想清楚复杂度再动手。如果感觉要写嵌套循环立刻停下来问自己一句“有没有线性做法”。Q1几乎没有需要嵌套循环的题一旦你发现自己写了双重循环大概率是思路偏了。及时止损比硬着头皮写完更重要。4.4 对拍验证的小工具经验如果你怀疑贪心正确性又不想严谨证明可以写一个O(n^2)的暴力BFS做对拍随机生成100组小数据跑暴力结果和贪心结果做对比全部一致就可以放心提交。这是我对付“看着对但心里没底”类问题的土办法多花两分钟省得交完WA再回来改。对拍的具体做法不复杂暴力就用一个bool数组标记可达从0开始每到一个点就把后面跳得到的点全部标记贪心就是上面的代码。随机数据里混合各种极端情况比如跳跃能力为0、全部可达、断点在中段。只要随机100组没有差异基本可以确认正确。这个习惯在打周赛时特别实用因为比赛环境不允许反复试错但对拍可以在本地保证一次AC。5. 避坑速查这些问题我替你踩过了5.1 为什么我的BFS超时因为你枚举了每个点向外jump[i]条边总边数是O(sum(jump))。把jump[i]放到最大数据一大必死。解决办法放弃显式建图用far线性扫描。这是最典型的“思路对但复杂度不对”的翻车。BFS适合图论题不适合这种一维区间扩张题。5.2 为什么我的DP也超时典型写法是dp[i]由前面k个状态转移复杂度O(nk)。如果n和k都是1e5循环次数1e10不超时才怪。改用“维护可达区间右端点”的贪心只需遍历一次。如果你确实想练DP可以用前缀和优化到O(n)但竞赛里没必要。记住能用O(n)O(1)解决就不要用O(n)O(n)。5.3 为什么贪心在某些case答案不对先检查两件事第一far是不是用当前塔i更新而不是用之前的某个塔第二是否在i刚大于far时就break。还有一个隐蔽错误有人在循环开头先更新far再判断i是否可达这样会把不可达的塔也当成可达。顺序必须是判断、记录、扩展。这三点我全踩过尤其第三点写成“先扩展再判断”的代码逻辑上是错的但小数据可能碰巧能过大数据就暴露了。5.4 相等高度的塔怎么处理这完全看题面。大多数题会写“如果有多个返回编号最小的”那么比较时用h[i] bestH只有严格大于才替换如果要求编号最大的就用。比赛时务必把输入输出示例里的平局情况看一遍。如果题目没有明说通常默认返回编号最小的因为初始化best_idx0天然满足这个要求。5.5 如果塔有坐标而不是下标那题目已经不是Q1强度。当塔的位置是任意x坐标时可达区间不再贴合数组下标需要按坐标排序后重新处理或者转成二维平面问题。出现这种情况先怀疑自己是不是看错题了。真正的Q1题目为了降低难度会刻意把塔排列成下标连续的一维数组避免坐标离散化这些额外步骤。6. 延伸思考一类题不是一道题6.1 跳跃游戏家族“可达最优”是一个很常见的问题框架。经典的有只问能否跳到终点维护far遍历完看far是否 n-1。问最少跳几步贪心按层扩展记录当前层的边界。本题问可达塔中最高/最好遍历时顺便维护最优值。共同点都是连续可达区间都用一个far搞定。你把这一个模型吃透等于同时会了好几个题。我刷题时有个习惯每做完一道题就想想它跟哪些经典题共享同一个核心模型把它们归成一组。这样复习的时候不用一题题看直接看模型就行。跳跃游戏这个模型清理一下可以覆盖七八道周赛题。6.2 如果加上高度差限制假设题目变成从塔i能跳到塔j除了距离限制还要求h[j] h[i] d。这时“能跳”不再只由距离决定可达集合可能不再连续贪心直接失效。正确做法是转成最短路或带限制的DP复杂度也会上一个台阶。这种变形是Q2或Q3的热门素材值得单独写一篇。为什么加上高度差限制后连续性就不成立了因为你可能从0跳到一座低塔再从低塔跳到一座不满足“从0直接跳”的高塔。从0看那座高塔是“不可达”的但换个路径就可达了。可达集合里出现了“洞”far模型就瓦解了。很多人刷题只记住模板没理解模板成立的前提条件结果题目一变就懵。这题刚好是个很好的反面教材值得多想一层。6.3 怎么让这题变成周赛的AC率陷阱这题区分度不在算法而在心态。高手扫一眼就写贪心新手容易一头扎进BFS/DFS。我见过不少人在Q1上耗了二三十分钟最后还没AC把整个比赛的节奏都带崩了。所以我的建议很直接遇到这种“可达最优”先画几笔看可达集合是不是区间是区间就贪心不是区间再上重武器。比赛节奏这件事说起来玄其实很实在。Q1正常应该在5分钟内AC超过10分钟就说明思路出问题了。这时候果断跳过做后面的题回头再想往往比死磕更有效率。双周赛每道题分值相同Q1和Q4一样重要没必要为了一道Q1丢了三道题的心态。当然如果你平时训练足够多“这题就是跳跃游戏变体”的判断会形成条件反射根本不会纠结。最后分享一个我自己的习惯。每次写完这种贪心扫描题我都会把“判断可达、更新答案、扩展边界”这三步的顺序在心里默念一遍再对着样例过一遍。看起来是小事但双周赛那种紧张状态下一个顺序写反就够你多花十分钟。把这题吃透之后你会发现跳跃游戏那一整个系列都顺了后面再遇到“加油站”“合并区间”这类问题也会更容易往连续区间的方向想。希望这篇还原思路对你有用赛场上见。 
长河君 · 2026/10/16 4:43:49 · 阅读 1.2k 最好可到达的塔：跳跃游戏变体的贪心扫描解法
第174场双周赛Q1题号100960题目叫“最好可到达的塔”。我第一眼看到这个标题脑子里已经把解法猜了个七七八八这题十有八九是“跳跃游戏”的变体——给你一堆塔从起点塔出发每座塔有各自的跳跃能力能跳到的塔就算可到达最后在可到达的塔里选一个“最好”的通常是高度最高的。Q1的定位决定了它不会太复杂核心考察点就两个怎么判断一个塔能不能到怎么在“能到”的集合里快速找最优。说实话这题的难度不在于算法本身有多深而在于很多人一上来就想复杂又是BFS又是DP最后写出一堆代码还超时。实际上这类“可达最优”的题目只要抓住“可达集合的连续性”这个性质一句话就能讲清楚解法。我按尚未拿到完整题面时的常见设定来还原思路你拿到的版本就算细节有出入比如跳跃力换成能量值核心方法一样适用。适合谁看如果你是刚开始打周赛的新手这篇能帮你建立“贪心扫描”的直觉如果是老手重点看后面边界处理和实战节奏的部分。1. 读懂“最好可到达的塔”三个关键词就是解题线索1.1 “塔”到底是什么从竞赛出题习惯来看“塔”就是一维数组里的元素。每座塔有两个关键属性一个是它自身的价值题目叫“最好”多半指高度、收益、分数这类可以比较大小的数值另一个是它的“跳跃能力”也就是从这座塔出发能向前跳多远。你从第0座塔起步跳着跳着就能到达一部分塔剩下那些超过跳跃范围的塔看着再高也跟你没关系。可能有人会问为什么不是二维坐标里的塔因为Q1的定位决定了数据结构和算法不能太复杂二维可达性问题动辄就是BFS加优先队列那是Q3、Q4的强度。一维数组加跳跃约束才是双周赛第一题的正确姿势。所以我下面所有讨论都以“塔排成一排下标从0开始”为前提。做这种题第一步不是写代码而是确认数据结构形态。很多新手看到“塔”字就脑补出平面地图然后开始建图、跑搜索直接把简单题做复杂了。我自己的习惯是先看输入描述里是“数组”“下标”还是“坐标”“网格”后者才需要考虑二维情况。数组类的“塔”先按一维区间问题处理Q1基本不会翻车。1.2 “可到达”的本质是区间而不是散点这是整道题最关键的性质。假设你站在塔i它最多能跳jump[i]步那么从i出发塔i1、i2、……、ijump[i]全都能直接到达。中间不存在“跳过一两个塔”的情况因为距离更短的跳跃一定也合法。这样一来所有能到达的塔连在一起一定是一个从0开始的连续区间。这个性质太重要了它直接决定了解法的复杂度。如果可达集合是散点你就必须老老实实BFS或者DP如果是连续区间那就只需要维护一个“能到达的最右边界”扫一遍数组完事。很多人卡在这题就是因为没想通“连续”这个点。我举个具体的例子塔0的跳跃能力是3那么塔1、塔2、塔3都直接可达。哪怕塔2的高度特别高你也不需要考虑“绕路”的问题因为从塔0直接一步就跳过去了。连续性的本质是“近处一定比远处更容易到达”这在单向、无消耗跳跃模型里永远成立。想通这一点后面所有代码都顺理成章。1.3 题目大概率的长相题面还原根据标题和Q1的定位原题大概率是下面这个形式我按最常见设定还原一下有n座塔排成一排下标从0到n-1。第i座塔的高度为h[i]最大跳跃距离为jump[i]。你初始在第0座塔从塔i可以跳到任意塔ji j i jump[i]。求所有可到达的塔中高度最高的塔的下标或高度。如果题目细节和我还原的不完全一样比如不是jump数组而是从起点给一个固定能量k、每跳一步消耗1那么只要把jump[i]换成固定的k即可贪心写法完全不变。这就是我说“细节有出入不影响思路”的原因。还有一个可能的变化是塔的高度本身充当跳跃能力比如能跳h[i]步那代码里连jump数组都省了直接用h[i]就行。但无论怎么变核心都是“从当前可达区间的最右端不断向外扩展”这个模型是稳定的。2. 思路演进从暴力BFS到一行贪心2.1 暴力BFS为什么能过但没必要最朴素的想法是建图每个点i向右连jump[i]条边然后从0出发BFS把所有能到的点标记出来最后遍历一遍找最高。正确性没问题但复杂度是O(n * max(jump))。如果n是10^5jump[i]平均也是10^5量级连边和遍历的规模就是10^10比赛环境必炸。就算用邻接表省掉连边BFS访问到的边数还是那么多。所以在Q1这个位置出题人摆明了想让你找线性做法。有同学可能会想Q1的数据范围会不会很小暴力能过这种侥幸心理要不得。双周赛第一题虽然简单但数据范围通常是1e5甚至2e5目的就是卡掉所有非线性的做法。你在比赛里赌数据弱不如直接想最优解反正贪心也就多花两分钟思考。2.2 用DP能不能做DP的思路也自然定义dp[i]表示塔i是否可达转移时看前面i-k到i-1范围内有没有可达的塔。写成代码就是内层循环扫窗口复杂度还是O(nk)跟BFS一个量级。但如果用“窗口内是否存在可达点”这个视角你会发现只需要维护一个变量到目前为止能到达的最右下标far。只要i far塔i就是可达的因为远方的塔都可达近处的塔不可能不可达。这就是把DP的窗口优化成了贪心。我见过有人写了一个“看起来很聪明”的DPdp[i]表示从0到i能否到达转移用前缀和优化把复杂度降到O(n)。这当然能AC但比贪心多花了三倍代码量。竞赛里Q1要的是最短时间AC能用O(n)O(1)空间的贪心就没必要写O(n)O(n)空间的DP。当然如果你一开始没想到贪心能用前缀和优化DP修正TLE也是一种本事至少比卡死强。2.3 贪心的正确性证明来严格说下为什么一个far就够了。定义far为当前已确认可达的塔的最大下标。初始far0。遍历i从0到n-1如果i far说明从前面所有可达点出发都够不到i而且由于可达下标是连续的i之后的所有塔也全都不可达直接break。如果i far塔i必然可达。此时更新far max(far, i jump[i])因为从i出发能覆盖到ijump[i]。这个更新过程其实就是在不断扩大“连续可达区间”的右端点。由于每个点最多被扫到一次整体O(n)。证明里最关键的一步是连续性一旦从某个可达点p能跳到q则p到q之间的所有点都可由p直接跳到因此不可能出现“中间有洞”的可达集合。建议你自己在纸上画几个例子把这条性质写清楚考试时就不虚。这个证明比经典跳跃游戏还简单因为跳跃游戏里每个点的跳跃能力不同而这里如果全体塔的jump都相同那far就是ik不断推进。即使jump不同连续性依然成立因为这跟“每个点能跳多远”无关只跟“距离更近一定可以跳”有关。想通这一层你就再也不会怀疑贪心漏解了。2.4 从“判断可达”到“顺便求最好”判断完可达求“最好”就简单了在遍历过程中只要i可达就把它跟当前最优高度比较更新答案。这里有个编码顺序的讲究必须先判断i far再更新答案最后扩展far。反过来写可能会在i不可达时错误地更新答案虽然最后答案不一定错但逻辑会乱调试时容易怀疑人生。我把这个顺序总结成三个短语先问“到没到”再比“谁更好”最后“往外扩”。下一次遇到类似题目直接套能省不少脑力。还有个小细节起点塔一定可达所以答案初始化为第0座塔的高度和编号。千万别把best_h初始化为0否则遇到负高度数据虽然这题一般不会或者所有塔都不可达的情况会返回一个不存在的答案。3. 代码实现三分钟写出AC版本3.1 Python写法与逐行解释def best_reachable_tower(h, jump): n len(h) far 0 best_h h[0] best_idx 0 for i in range(n): if i far: break if h[i] best_h: best_h h[i] best_idx i far max(far, i jump[i]) return best_idxfar初始0代表第0座塔一定可达。best_h和best_idx初始化为第0座塔的信息因为起点也算可到达的塔如果后续没有更高的答案就是它。循环里先判断i是否还落在可达区间内再比较高度最后用当前塔的跳跃能力扩大边界。返回下标。如果题目要求1-based输出前1。Python版本要注意的点是如果h是空数组代码会崩但竞赛题n至少为1。另外如果h[i]可能相等而你被要求返回编号最大的那个就把比较从h[i] best_h改成h[i] best_h这样后出现的相等高度会覆盖之前的答案。这个细节看题面别惯性写成严格大于。3.2 C写法与类型细节int bestReachableTower(vectorint h, vectorint jump) { int n (int)h.size(); int far 0; int bestH h[0], bestIdx 0; for (int i 0; i n; i) { if (i far) break; if (h[i] bestH) { bestH h[i]; bestIdx i; } far max(far, i jump[i]); } return bestIdx; }C这边唯一要注意的是i jump[i]可能超过int表示范围虽然这题一般不会但遇到变体题jump[i]给到1e9时建议把far和i都用long long。另外vector传引用避免拷贝尤其当n是2e5时传值拷贝会白白增加O(n)开销虽然对于这题不至于TLE但养成好习惯没坏处。在代码风格上我建议把输出格式提前确认好。题目如果问“最高的塔的高度”那返回best_h如果问“最高的塔的编号”返回best_idx如果问“从0到该塔需要跳几步”那这题就变成另一个问题了。Q1一般只问高度或编号不会问步数但读题时别跳着看。3.3 边界情况对照表场景期望行为n1只有起点塔返回它的下标0jump[0]0只能停留在起点后面全部不可达最高塔落在断裂点之后不能选它答案应该是断裂前最高塔多座塔等高按题意取编号最小或最大严格大于区分起点塔本身就是最高的返回0不要漏掉初始化答案这些边界我在比赛时几乎每次都踩一遍尤其是n1和jump全0的情况。很多同学的代码在这些数据上不是越界就是答案错误本质上都是没把“起点塔必达”这个前提想明白。偷懒的办法是提交前先自己在脑子里跑一遍最小数据n1的时候循环只执行一次far不变答案是0这样就稳了。4. 竞赛实战从读题到AC的完整节奏4.1 读题阶段提取什么双周赛第一题的目标不是“做出来”而是“快速做出来”给后面难题留时间。读题时我用十秒圈出三样东西起始条件从哪出发、移动规则怎么算可达、目标函数比高度还是比编号。题目里只要出现“最远能跳几步”“能到达的塔”“最高/最好”这类词基本就是跳跃游戏变体解法直接锁定贪心。这里有个经验之谈Q1的题面一般都很短但越短越要逐字读。我曾经因为漏看“高度相同返回编号较大”这句话多交了两发WA。比赛界面没有编译器提示WA一次就是五分钟惩罚对心态的打击比分数还大。所以读题宁可慢十秒也不要因为粗心多花五分钟。4.2 手搓样例与极端数据验证写完代码先别急着提交在本地随手造几组数据试全0跳跃能力far永远是0循环在i1时break答案起点。跳跃能力递增所有塔可达答案最高塔。断裂点靠前最高塔在断点后验证不会被选到。最高塔在起点验证初始化逻辑正确。这组验证30秒做完能规避八成提交错误。尤其是“断裂点靠前”这个数据能直接看出你的break逻辑有没有写对。如果你发现答案选到了断点后面的塔那一定是在i far时没有break或者是用不可达的i更新了far。这种低级错误在紧张状态下特别容易犯本地跑一下就能抓出来。4.3 现场翻车最常见的三种姿势一是写了DP但是内层循环给了k一测大数据直接TLE然后才想起来有贪心二是输出高度而不是下标或者反过来白白吃一发WA三是“相等高度时输出编号最大”没注意到被题目细节坑。这些都是可以靠读题规避的低级失误。我自己的现场策略是看到这题类型后先花30秒想清楚复杂度再动手。如果感觉要写嵌套循环立刻停下来问自己一句“有没有线性做法”。Q1几乎没有需要嵌套循环的题一旦你发现自己写了双重循环大概率是思路偏了。及时止损比硬着头皮写完更重要。4.4 对拍验证的小工具经验如果你怀疑贪心正确性又不想严谨证明可以写一个O(n^2)的暴力BFS做对拍随机生成100组小数据跑暴力结果和贪心结果做对比全部一致就可以放心提交。这是我对付“看着对但心里没底”类问题的土办法多花两分钟省得交完WA再回来改。对拍的具体做法不复杂暴力就用一个bool数组标记可达从0开始每到一个点就把后面跳得到的点全部标记贪心就是上面的代码。随机数据里混合各种极端情况比如跳跃能力为0、全部可达、断点在中段。只要随机100组没有差异基本可以确认正确。这个习惯在打周赛时特别实用因为比赛环境不允许反复试错但对拍可以在本地保证一次AC。5. 避坑速查这些问题我替你踩过了5.1 为什么我的BFS超时因为你枚举了每个点向外jump[i]条边总边数是O(sum(jump))。把jump[i]放到最大数据一大必死。解决办法放弃显式建图用far线性扫描。这是最典型的“思路对但复杂度不对”的翻车。BFS适合图论题不适合这种一维区间扩张题。5.2 为什么我的DP也超时典型写法是dp[i]由前面k个状态转移复杂度O(nk)。如果n和k都是1e5循环次数1e10不超时才怪。改用“维护可达区间右端点”的贪心只需遍历一次。如果你确实想练DP可以用前缀和优化到O(n)但竞赛里没必要。记住能用O(n)O(1)解决就不要用O(n)O(n)。5.3 为什么贪心在某些case答案不对先检查两件事第一far是不是用当前塔i更新而不是用之前的某个塔第二是否在i刚大于far时就break。还有一个隐蔽错误有人在循环开头先更新far再判断i是否可达这样会把不可达的塔也当成可达。顺序必须是判断、记录、扩展。这三点我全踩过尤其第三点写成“先扩展再判断”的代码逻辑上是错的但小数据可能碰巧能过大数据就暴露了。5.4 相等高度的塔怎么处理这完全看题面。大多数题会写“如果有多个返回编号最小的”那么比较时用h[i] bestH只有严格大于才替换如果要求编号最大的就用。比赛时务必把输入输出示例里的平局情况看一遍。如果题目没有明说通常默认返回编号最小的因为初始化best_idx0天然满足这个要求。5.5 如果塔有坐标而不是下标那题目已经不是Q1强度。当塔的位置是任意x坐标时可达区间不再贴合数组下标需要按坐标排序后重新处理或者转成二维平面问题。出现这种情况先怀疑自己是不是看错题了。真正的Q1题目为了降低难度会刻意把塔排列成下标连续的一维数组避免坐标离散化这些额外步骤。6. 延伸思考一类题不是一道题6.1 跳跃游戏家族“可达最优”是一个很常见的问题框架。经典的有只问能否跳到终点维护far遍历完看far是否 n-1。问最少跳几步贪心按层扩展记录当前层的边界。本题问可达塔中最高/最好遍历时顺便维护最优值。共同点都是连续可达区间都用一个far搞定。你把这一个模型吃透等于同时会了好几个题。我刷题时有个习惯每做完一道题就想想它跟哪些经典题共享同一个核心模型把它们归成一组。这样复习的时候不用一题题看直接看模型就行。跳跃游戏这个模型清理一下可以覆盖七八道周赛题。6.2 如果加上高度差限制假设题目变成从塔i能跳到塔j除了距离限制还要求h[j] h[i] d。这时“能跳”不再只由距离决定可达集合可能不再连续贪心直接失效。正确做法是转成最短路或带限制的DP复杂度也会上一个台阶。这种变形是Q2或Q3的热门素材值得单独写一篇。为什么加上高度差限制后连续性就不成立了因为你可能从0跳到一座低塔再从低塔跳到一座不满足“从0直接跳”的高塔。从0看那座高塔是“不可达”的但换个路径就可达了。可达集合里出现了“洞”far模型就瓦解了。很多人刷题只记住模板没理解模板成立的前提条件结果题目一变就懵。这题刚好是个很好的反面教材值得多想一层。6.3 怎么让这题变成周赛的AC率陷阱这题区分度不在算法而在心态。高手扫一眼就写贪心新手容易一头扎进BFS/DFS。我见过不少人在Q1上耗了二三十分钟最后还没AC把整个比赛的节奏都带崩了。所以我的建议很直接遇到这种“可达最优”先画几笔看可达集合是不是区间是区间就贪心不是区间再上重武器。比赛节奏这件事说起来玄其实很实在。Q1正常应该在5分钟内AC超过10分钟就说明思路出问题了。这时候果断跳过做后面的题回头再想往往比死磕更有效率。双周赛每道题分值相同Q1和Q4一样重要没必要为了一道Q1丢了三道题的心态。当然如果你平时训练足够多“这题就是跳跃游戏变体”的判断会形成条件反射根本不会纠结。最后分享一个我自己的习惯。每次写完这种贪心扫描题我都会把“判断可达、更新答案、扩展边界”这三步的顺序在心里默念一遍再对着样例过一遍。看起来是小事但双周赛那种紧张状态下一个顺序写反就够你多花十分钟。把这题吃透之后你会发现跳跃游戏那一整个系列都顺了后面再遇到“加油站”“合并区间”这类问题也会更容易往连续区间的方向想。希望这篇还原思路对你有用赛场上见。