如果你准备过互联网公司的研发岗校招大概率在牛客网上见过“网易2016研发工程师编程题”这套题。它不算难却是我见过最值得反复刷的入门套题之一。里面有小易的升级之路、瞌睡、奖学金、路灯这几道经典题分别对应模拟、滑动窗口、贪心和边界处理。今天就把这套题完整拆一遍讲清楚每道题的核心思路、为什么这么做、代码怎么写以及我在实际刷题中踩过的坑。这套题最大的价值不是让你背答案而是用一种很“实在”的方式帮你把校招笔试最基础、最高频的几种能力过一遍。很多同学一上来就刷 hard 题结果笔试现场连这种 medium 偏下的题都写不稳实在可惜。先把这套题吃透再去碰复杂的动态规划和图论节奏会顺很多。1. 这套题到底在筛选什么能力1.1 为什么网易2016的题现在还值得刷先说结论技术面试的题库会变但基础题的考法变化很慢。网易2016研发工程师编程题属于典型的“校招基准难度”样本——不考冷门算法不玩文字游戏就是用最简单的方式考察你读题、建模、写码、调试这几项基本功。很多同学觉得题目是2016年的太老没参考价值。但实际上现在大厂笔试的前两三题难度和风格跟这套题高度重合。比如某某厂考“给定一个数组和一个窗口长度求窗口内某些条件的最小值/最大值”本质上就是瞌睡这道题的变体再比如考“背包问题的简化版每件物品有容量上限和单位成本用最小总成本满足目标”奖学金就是它的雏形。所以这套题不是用来“考古”的它是用来做能力标定的。你如果能独立、快速、稳定地写出这几道题说明你的笔试基本盘是稳的如果写起来磕磕绊绊那正好借这套题把薄弱环节补齐。1.2 四道题背后隐藏的四种基本能力我把这套题的核心考点整理了一张表方便你对照检查题目核心考点难度最容易踩的坑小易的升级之路模拟、数据范围简单想复杂以为需要排序或贪心瞌睡滑动窗口、前缀和中等窗口初始化错、额外收益算重复奖学金贪心、排序中等目标差算错、排序方向反了路灯排序、边界处理简单偏中等忘了两端、忘记除以2从这张表能看出来网易这套题不喜欢堆砌知识点特别喜欢在“简单考点 边界情况”上做文章。比如路灯这题算法思路一句话就能说完但至少有30%的人第一次提交会挂在端点处理上。这其实是在筛选一种工程思维你写代码时到底想没想过数据在边界情况下是什么表现。我一直觉得刷题的核心不是比谁见过的题多而是比谁在简单题上更稳。这套题就是在帮你练这个“稳”字。2. 升级之路、瞌睡、奖学金、路灯逐题拆解2.1 小易的升级之路为什么“能打就打”就是最优解题目描述很直白小易初始能力值为 a按顺序遇到 n 个怪物每个怪物战斗力为 x[i]。如果当前能力值不低于怪物战斗力就能打败它并获得 x[i] 的能力值否则只能跳过。求最终能力值。我第一次看到这题第一反应是是不是需要先排序把弱小的怪物先打了增强实力再打强的如果你也这么想恭喜你掉进了一个典型的“想太多”陷阱。题目里写得很清楚小易是按顺序遇到怪物的不是让你从怪物堆里挑着打。关键要理解一件事打败怪物永远是净收益能力值只会增加不会减少也没有任何负面代价。所以只要是能打过的怪物立刻打掉一定不亏。你可能会想现在打掉这个怪物会不会导致后面某个本来能打过的怪物反而打不过了不会因为你的能力值只会因为打败怪物而变高变高了只会更容易打不可能更难打。所以“能打就打”就是最优策略不需要排序不需要选择直接模拟即可。代码也很简单我直接给可运行的版本import sys def solve(): data sys.stdin.read().strip().split() if not data: return idx 0 out [] while idx len(data): n int(data[idx]); idx 1 a int(data[idx]); idx 1 for _ in range(n): x int(data[idx]); idx 1 if x a: a x out.append(str(a)) print(\n.join(out)) if __name__ __main__: solve()复杂度是 O(n)完全够用。这里要注意一个问题初始能力值和怪物战斗力都可能比较大累计之后可能超出 int 的范围。用 Python 虽然不用操心溢出但如果用 C 或 Java记得开 long long / long。我当时就见过有人用 int 写样例过了一提交就 WA就是因为这个。这道题想明白之后你会发现它其实是“贪心思想的雏形”——局部最优操作不损害全局利益所以直接做就是全局最优。这种“无后效性”的思维方式后面做更复杂的贪心题也经常用到。2.2 瞌睡滑动窗口的本质是“一次性增量”这道题的场景很有意思一节课共 n 分钟第 i 分钟小易对知识的兴趣程度为 a[i]每分钟的清醒状态为 b[i]1 表示清醒0 表示瞌睡。清醒的时候他能获得对应的兴趣值瞌睡的时候收益为 0。他可以在某一时刻叫醒自己并持续 k 分钟。求整节课能获得的最大兴趣值。这题的暴力做法是枚举叫醒的起始位置然后对每个长度为 k 的窗口重新求和复杂度 O(nk)。当 n 到 10^5 级别时必挂。正确的做法是把它拆成两部分第一部分是“本来就清醒”的收益这部分是固定的怎么叫醒都不会改变。先算出来base sum(a[i] for i in range(n) if b[i] 1)。第二部分是“因为叫醒而多拿”的收益。如果某个长度为 k 的连续时间段内某些分钟本来是瞌睡的叫醒之后这些分钟就从 0 变成 a[i]所以额外收益就是窗口内所有 b[i]0 的 a[i] 之和。我们要在整节课上找一个长度为 k 的窗口让这个额外收益最大。于是问题变成了标准的滑动窗口。先算第一个窗口 [0, k-1] 的额外收益然后窗口每向右移动一格就加上新进入窗口的瞌睡分钟兴趣值减去离开窗口的瞌睡分钟兴趣值同时更新最大值。import sys def solve(): data sys.stdin.read().strip().split() if not data: return idx 0 n int(data[idx]); idx 1 k int(data[idx]); idx 1 a [] for _ in range(n): a.append(int(data[idx])); idx 1 b [] for _ in range(n): b.append(int(data[idx])); idx 1 base sum(a[i] for i in range(n) if b[i] 1) extra 0 for i in range(k): if b[i] 0: extra a[i] max_extra extra for i in range(k, n): if b[i] 0: extra a[i] if b[i - k] 0: extra - a[i - k] if extra max_extra: max_extra extra print(base max_extra) if __name__ __main__: solve()注意窗口滑动的边界初始窗口是 [0, k-1]循环从 ik 开始每次加入 a[i]、移出 a[i-k]新窗口就是 [i-k1, i]。我见过很多人把初始窗口写成 [1, k]或者循环边界写成 range(k, n-1)结果样例都过不了。这道题想明白之后你就掌握了滑动窗口的核心思想与其每次重新计算整个窗口不如只处理“变化的部分”。这个思想在后面做“无重复最长子串”“最小覆盖子串”等经典题时极其重要。2.3 奖学金贪心但是要先把目标量化奖学金这题的题面在不同版本里略有差异我按我见过的常见版本来讲小易有 n 门课每门课当前成绩为 a[i]满分为 r每复习一小时可以使某门课的成绩提高 1 分但不会超过满分。每门课提高 1 分需要的时间还不一样用 b[i] 表示。要想平均分达到 avg最少需要复习多少小时先把目标量化。现在总成绩是 sum(a[i])目标总成绩是 n * avg所以还差 need n * avg - sum(a[i])。如果 need 已经小于等于 0直接输出 0。接下来问题变成有 n 门课每门课最多还能提高 r - a[i] 分要提高 1 分需要 b[i] 小时怎么在凑够 need 分的前提下让总复习时间最少这就是一个经典的贪心模型。每门课提高 1 分的效果是等价的——都是让总分增加 1所以我们要优先选择“提高 1 分需要时间更少”的课程来复习。每门课可以往上提高的范围有限所以是一门课一门课地“买分”买到上限就换下一门性价比稍低的课。import sys def solve(): data sys.stdin.read().strip().split() if not data: return idx 0 out [] while idx len(data): n int(data[idx]); idx 1 r int(data[idx]); idx 1 avg int(data[idx]); idx 1 courses [] total 0 for _ in range(n): ai int(data[idx]) bi int(data[idx 1]) idx 2 courses.append((ai, bi)) total ai need n * avg - total if need 0: out.append(0) continue courses.sort(keylambda x: x[1]) ans 0 for ai, bi in courses: add min(r - ai, need) ans add * bi need - add if need 0: break out.append(str(ans)) print(\n.join(out)) if __name__ __main__: solve()贪心的正确性这里多说一句这不是那种“看起来差不多”的贪心而是可以严格证明的。因为每门课提高分数的单位成本是固定的且在达到满分之前可以任意增量购买所以要让总成本最小必然是按单位成本从小到大依次购买。你可以把它理解成“分数版”的分数背包问题只不过每件物品可以拆成 1 分 1 分地买。踩坑重点有两个第一个是排序方向。按 b[i] 从小到大排也就是把“性价比高”的课程放前面。我见过有人按 a[i] 排序或者按 r - a[i] 排序那都是不对的。第二个是循环里 add min(r - ai, need) 的 min 不能漏否则会把某门课提高到超过满分答案就会偏大。最后注意 n * avg 可能很大建议用 64 位整数。2.4 路灯排序后答案藏在三个距离里最后一个题是路灯一条长度为 l 的街道有 n 个路灯位置是 pos[i]路灯的照明半径是 d问最小的 d 是多少才能让整条街道都被照亮。先把路灯位置排序。排序之后问题就变得很清晰了。三类限制决定了 d 的下限第一街道起点 0 必须被照亮。离起点最近的路灯是 pos[0]所以 d 至少是 pos[0]。第二街道终点 l 必须被照亮。离终点最近的路灯是 pos[-1]所以 d 至少是 l - pos[-1]。第三相邻两个路灯之间的空白区域必须被照亮。如果两个路灯的位置分别是 pos[i] 和 pos[i1]那么它们之间的空白长度为 pos[i1] - pos[i]这两个灯各负责一半所以 d 至少是 (pos[i1] - pos[i]) / 2。最终的答案就是这三类距离的最大值。import sys def solve(): data sys.stdin.read().strip().split() if not data: return idx 0 out [] while idx len(data): n int(data[idx]); idx 1 l int(data[idx]); idx 1 pos [] for _ in range(n): pos.append(int(data[idx])); idx 1 pos.sort() ans max(pos[0], l - pos[-1]) for i in range(1, n): ans max(ans, (pos[i] - pos[i - 1]) / 2.0) out.append(f{ans:.2f}) print(\n.join(out)) if __name__ __main__: solve()这道题看起来简单但能踩的坑不少。最常见的两个一是忘记处理两端只算了相邻距离的一半二是相邻距离没有除以 2直接把整段距离当成半径。如果你把这两个坑都躲开了这道题基本就是送分题。另外注意输出格式题目一般要求保留两位小数用 f{ans:.2f} 格式化不要手写四舍五入的逻辑。3. 完整可运行的参考代码与验证过程3.1 如何用 Python 快速跑通所有题目上面我给的代码都是可以独立运行的。这里说一下输入处理的通用模板。牛客笔试的输入往往有多组测试用例但不会显式告诉你组数最常见的方式是“读取到文件末尾”也就是 EOF。用 sys.stdin.read() 一次性读取所有数据然后用一个 idx 指针按顺序解析是最省心的方式。这个模板的好处有三个第一你不用关心输入到底有几行反正按顺序取第二解析速度快不会像 input() 逐行读那样在高数据量下拖后腿第三代码结构统一不容易漏读。3.2 用样例验证输出为了让你看得更清楚我把每道题的样例跑一遍。小易的升级之路输入2 5 3 2解析出来是 n2a5怪物战斗力是 3 和 2。第一个怪物战斗力 3 小于等于 5打掉能力变成 8第二个怪物战斗力 2 小于等于 8打掉能力变成 10。输出 10。瞌睡输入6 3 1 3 5 2 5 4 1 1 0 1 0 0清醒时刻的基础收益是 a[0]a[1]a[3] 132 6。然后找长度为 3 的窗口窗口 [2,4] 的额外收益最大覆盖的是下标 2 的 5 和下标 4 的 5额外收益是 10。最终答案 16。奖学金输入3 100 80 70 10 50 20 80 5当前总分 200目标总分 240还差 40 分。按每提高 1 分需要的时间排序80 分的课成本是 5先提高 20 分到满分花 100 小时70 分的课成本是 10再提高 20 分到 90花 200 小时。总时间 300这时平均分正好 80。输出 300。路灯输入2 15 5 10排序后路灯在 5 和 10。d 至少覆盖起点5至少覆盖终点15-105相邻距离的一半(10-5)/22.5。最大值是 5输出 5.00。这四组样例都可以直接粘贴到代码里验证结果和我写的一致。3.3 从 Python 移植到 C 的注意事项如果你笔试允许选 Python 那当然好但有些公司默认用 C所以我还是提醒几个移植要点。输入输出方面建议用 scanf/printf或者关掉 C 流同步后使用 cin/cout。数据范围方面能力值、总分差、最终答案都可能超过 2^31-1用 long long。浮点输出方面路灯题用 printf(%.2lf\n, ans)不要用 float用 double。C 写小易的升级之路核心循环就是while (n--) { long long x; scanf(%lld, x); if (x a) a x; }奖学金的多组数据处理记得在循环内初始化 total、need、ans不然很容易带着上一组的数据继续算。4. 我刷这套题时踩过的坑与排查技巧4.1 输入处理的坑我见过最多的问题不是算法不会而是多组输入处理不对。有些同学用 input() 一行一行读遇到第一行数据读完后以为结束了结果下一组测试数据读不到直接报错。解决办法就是用 sys.stdin.read() 一次读完再用指针切分。这种“流式解析”的思路在校招笔试里非常实用尤其是题目不说有几组数据的时候。另外一个细节是 read() 读完可能是空字符串记得先 strip()否则 split() 会返回空列表循环直接跳过。4.2 数据范围和溢出小易的升级之路里怪物战斗力可能叠加到很大奖学金里 n * avg 也可能很大。用 int 存这些值的后果是本地样例正常一提交 WA或者出现负数完全看不出来哪里错了。排查方法很简单把所有可能累加的变量都改成 64 位整数。在 Python 里没这个问题但我还是建议你养成习惯凡是涉及总和、乘积、累计优先考虑数据范围。4.3 滑动窗口边界初始化瞌睡这题窗口边界错了很难查。初始化 extra 的时候要算前 k 个元素循环从 k 开始到 n-1先加新元素再删旧元素。顺序不能反反了会重复计算或者漏算。我提供一个自查方法拿一个很小的 n 和 k比如 n3, k2手动在纸上把窗口滑一遍对着代码验证每一步的额外收益。滑动窗口这种题边界不出错的最快方式就是先用小数据手动模拟一遍。4.4 贪心排序方向错误奖学金这题排序方向错了会得到完全错误的答案。我见过有同学按当前成绩 a[i] 排序想着“先把成绩低的补上去”听起来好像有道理但成本不同这么做就不对。比如一门课 90 分提高 1 分需要 100 小时另一门课 30 分提高 1 分只需要 1 小时按成绩排序会先补 90 分那门明显不合理。遇到贪心题先别急着写排序先问自己排序的关键指标是什么这里的指标是“把总分提高 1 分需要付出多少小时”所以要按 b[i] 排序。如果题目没有 b[i] 这个成本所有课提高 1 分的时间都一样才不需要排序。4.5 路灯浮点精度与输出格式路灯这题的输出要求保留两位小数直接 printf(%.2f) 即可。常见的问题是有人把相邻距离除以 2 之后存成 float然后又拿去和 int 比较这时候 C 会做隐式转换结果可能不对。我建议在整个计算过程中统一用 double。另外如果答案本来就是整数比如两端距离是 5输出也应该写成 5.00不要输出 5格式不对照样判错。下面把这几类问题整理成一张排查速查表现象可能原因解决办法升级之路输出异常负数int 溢出改 long long / long瞌睡额外收益偏大或偏小窗口初始化或滑动顺序错误先手动模拟小数据奖学金答案明显过大排序方向错误或漏了 min 上限按成本排序加 min 限制路灯答案少了端点覆盖没算 pos[0] 和 l-pos[-1]三类限制都取最大值输出格式不对没保留两位小数用 printf(%.2f) 或 f-string5. 刷完这套题之后下一步往哪走5.1 从这套题看大厂笔试的出题逻辑很多同学刷题有个误区总觉得笔试会考特别偏的算法于是花大量时间堆冷门知识点。实际上绝大多数大厂的校招笔试前面的题目难度就是网易2016这套题的级别重点考察的是你能否把题目描述翻译成代码逻辑能否在边界条件下保持正确能否在时间复杂度上不犯低级错误。说到底笔试筛掉的不是“不会难题的人”而是“连简单题都写不稳的人”。这套题的价值就在于帮你把基础盘打扎实让你在真正笔试时看到同类题目能快速建立思路。5.2 每个考点对应的进阶题目刷完这套题如果你想继续深挖每个考点都有对应的进阶题可以去练。模拟题的进阶方向是“大模拟”比如螺旋矩阵、旋转数组、Z 字形变换这类题不考算法考的是代码组织能力和细心程度。滑动窗口的进阶方向是无重复最长子串、最小覆盖子串这两道题是面试高频。贪心的进阶方向是区间调度、跳跃游戏核心还是那个问题每一步的最优选择是什么这个选择会不会影响后面的选择。边界处理的进阶方向是二分查找的各种变体你会发现很多二分题不是死在算法上而是死在 left、right、mid 的边界更新上。5.3 给校招同学的刷题节奏建议我个人建议的节奏是先把这套网易2016题独立做一遍不要看题解哪怕花一整天也要自己写出来。不会的题标记好过两天再独立写一遍。这样两遍下来你对“模拟、滑动窗口、贪心、边界处理”这四类基本能力会有一个很踏实的掌握。之后再去刷更系统的题单比如按公司分类的真题、按算法分类的题单、按难度递进的热题 100 题。每一道题做完之后都想一个问题这道题和之前做过的哪道题在思路上是相通的这种“归因”训练比盲目刷题效率高得多。我在实际刷题中最深的体会是笔试很多时候拼的不是灵光一闪而是稳定输出。像这套题里的路灯、奖学金思路都不难但真正能在 20 分钟内把边界全部处理对、一次提交通过的人其实没有想象中那么多。你不要追求刷题数量有多吓人先把这类基础题做到“闭着眼都不会错”后面再碰复杂题心态会完全不一样。
网易2016研发工程师编程题全解析：四大核心考点与刷题技巧
如果你准备过互联网公司的研发岗校招大概率在牛客网上见过“网易2016研发工程师编程题”这套题。它不算难却是我见过最值得反复刷的入门套题之一。里面有小易的升级之路、瞌睡、奖学金、路灯这几道经典题分别对应模拟、滑动窗口、贪心和边界处理。今天就把这套题完整拆一遍讲清楚每道题的核心思路、为什么这么做、代码怎么写以及我在实际刷题中踩过的坑。这套题最大的价值不是让你背答案而是用一种很“实在”的方式帮你把校招笔试最基础、最高频的几种能力过一遍。很多同学一上来就刷 hard 题结果笔试现场连这种 medium 偏下的题都写不稳实在可惜。先把这套题吃透再去碰复杂的动态规划和图论节奏会顺很多。1. 这套题到底在筛选什么能力1.1 为什么网易2016的题现在还值得刷先说结论技术面试的题库会变但基础题的考法变化很慢。网易2016研发工程师编程题属于典型的“校招基准难度”样本——不考冷门算法不玩文字游戏就是用最简单的方式考察你读题、建模、写码、调试这几项基本功。很多同学觉得题目是2016年的太老没参考价值。但实际上现在大厂笔试的前两三题难度和风格跟这套题高度重合。比如某某厂考“给定一个数组和一个窗口长度求窗口内某些条件的最小值/最大值”本质上就是瞌睡这道题的变体再比如考“背包问题的简化版每件物品有容量上限和单位成本用最小总成本满足目标”奖学金就是它的雏形。所以这套题不是用来“考古”的它是用来做能力标定的。你如果能独立、快速、稳定地写出这几道题说明你的笔试基本盘是稳的如果写起来磕磕绊绊那正好借这套题把薄弱环节补齐。1.2 四道题背后隐藏的四种基本能力我把这套题的核心考点整理了一张表方便你对照检查题目核心考点难度最容易踩的坑小易的升级之路模拟、数据范围简单想复杂以为需要排序或贪心瞌睡滑动窗口、前缀和中等窗口初始化错、额外收益算重复奖学金贪心、排序中等目标差算错、排序方向反了路灯排序、边界处理简单偏中等忘了两端、忘记除以2从这张表能看出来网易这套题不喜欢堆砌知识点特别喜欢在“简单考点 边界情况”上做文章。比如路灯这题算法思路一句话就能说完但至少有30%的人第一次提交会挂在端点处理上。这其实是在筛选一种工程思维你写代码时到底想没想过数据在边界情况下是什么表现。我一直觉得刷题的核心不是比谁见过的题多而是比谁在简单题上更稳。这套题就是在帮你练这个“稳”字。2. 升级之路、瞌睡、奖学金、路灯逐题拆解2.1 小易的升级之路为什么“能打就打”就是最优解题目描述很直白小易初始能力值为 a按顺序遇到 n 个怪物每个怪物战斗力为 x[i]。如果当前能力值不低于怪物战斗力就能打败它并获得 x[i] 的能力值否则只能跳过。求最终能力值。我第一次看到这题第一反应是是不是需要先排序把弱小的怪物先打了增强实力再打强的如果你也这么想恭喜你掉进了一个典型的“想太多”陷阱。题目里写得很清楚小易是按顺序遇到怪物的不是让你从怪物堆里挑着打。关键要理解一件事打败怪物永远是净收益能力值只会增加不会减少也没有任何负面代价。所以只要是能打过的怪物立刻打掉一定不亏。你可能会想现在打掉这个怪物会不会导致后面某个本来能打过的怪物反而打不过了不会因为你的能力值只会因为打败怪物而变高变高了只会更容易打不可能更难打。所以“能打就打”就是最优策略不需要排序不需要选择直接模拟即可。代码也很简单我直接给可运行的版本import sys def solve(): data sys.stdin.read().strip().split() if not data: return idx 0 out [] while idx len(data): n int(data[idx]); idx 1 a int(data[idx]); idx 1 for _ in range(n): x int(data[idx]); idx 1 if x a: a x out.append(str(a)) print(\n.join(out)) if __name__ __main__: solve()复杂度是 O(n)完全够用。这里要注意一个问题初始能力值和怪物战斗力都可能比较大累计之后可能超出 int 的范围。用 Python 虽然不用操心溢出但如果用 C 或 Java记得开 long long / long。我当时就见过有人用 int 写样例过了一提交就 WA就是因为这个。这道题想明白之后你会发现它其实是“贪心思想的雏形”——局部最优操作不损害全局利益所以直接做就是全局最优。这种“无后效性”的思维方式后面做更复杂的贪心题也经常用到。2.2 瞌睡滑动窗口的本质是“一次性增量”这道题的场景很有意思一节课共 n 分钟第 i 分钟小易对知识的兴趣程度为 a[i]每分钟的清醒状态为 b[i]1 表示清醒0 表示瞌睡。清醒的时候他能获得对应的兴趣值瞌睡的时候收益为 0。他可以在某一时刻叫醒自己并持续 k 分钟。求整节课能获得的最大兴趣值。这题的暴力做法是枚举叫醒的起始位置然后对每个长度为 k 的窗口重新求和复杂度 O(nk)。当 n 到 10^5 级别时必挂。正确的做法是把它拆成两部分第一部分是“本来就清醒”的收益这部分是固定的怎么叫醒都不会改变。先算出来base sum(a[i] for i in range(n) if b[i] 1)。第二部分是“因为叫醒而多拿”的收益。如果某个长度为 k 的连续时间段内某些分钟本来是瞌睡的叫醒之后这些分钟就从 0 变成 a[i]所以额外收益就是窗口内所有 b[i]0 的 a[i] 之和。我们要在整节课上找一个长度为 k 的窗口让这个额外收益最大。于是问题变成了标准的滑动窗口。先算第一个窗口 [0, k-1] 的额外收益然后窗口每向右移动一格就加上新进入窗口的瞌睡分钟兴趣值减去离开窗口的瞌睡分钟兴趣值同时更新最大值。import sys def solve(): data sys.stdin.read().strip().split() if not data: return idx 0 n int(data[idx]); idx 1 k int(data[idx]); idx 1 a [] for _ in range(n): a.append(int(data[idx])); idx 1 b [] for _ in range(n): b.append(int(data[idx])); idx 1 base sum(a[i] for i in range(n) if b[i] 1) extra 0 for i in range(k): if b[i] 0: extra a[i] max_extra extra for i in range(k, n): if b[i] 0: extra a[i] if b[i - k] 0: extra - a[i - k] if extra max_extra: max_extra extra print(base max_extra) if __name__ __main__: solve()注意窗口滑动的边界初始窗口是 [0, k-1]循环从 ik 开始每次加入 a[i]、移出 a[i-k]新窗口就是 [i-k1, i]。我见过很多人把初始窗口写成 [1, k]或者循环边界写成 range(k, n-1)结果样例都过不了。这道题想明白之后你就掌握了滑动窗口的核心思想与其每次重新计算整个窗口不如只处理“变化的部分”。这个思想在后面做“无重复最长子串”“最小覆盖子串”等经典题时极其重要。2.3 奖学金贪心但是要先把目标量化奖学金这题的题面在不同版本里略有差异我按我见过的常见版本来讲小易有 n 门课每门课当前成绩为 a[i]满分为 r每复习一小时可以使某门课的成绩提高 1 分但不会超过满分。每门课提高 1 分需要的时间还不一样用 b[i] 表示。要想平均分达到 avg最少需要复习多少小时先把目标量化。现在总成绩是 sum(a[i])目标总成绩是 n * avg所以还差 need n * avg - sum(a[i])。如果 need 已经小于等于 0直接输出 0。接下来问题变成有 n 门课每门课最多还能提高 r - a[i] 分要提高 1 分需要 b[i] 小时怎么在凑够 need 分的前提下让总复习时间最少这就是一个经典的贪心模型。每门课提高 1 分的效果是等价的——都是让总分增加 1所以我们要优先选择“提高 1 分需要时间更少”的课程来复习。每门课可以往上提高的范围有限所以是一门课一门课地“买分”买到上限就换下一门性价比稍低的课。import sys def solve(): data sys.stdin.read().strip().split() if not data: return idx 0 out [] while idx len(data): n int(data[idx]); idx 1 r int(data[idx]); idx 1 avg int(data[idx]); idx 1 courses [] total 0 for _ in range(n): ai int(data[idx]) bi int(data[idx 1]) idx 2 courses.append((ai, bi)) total ai need n * avg - total if need 0: out.append(0) continue courses.sort(keylambda x: x[1]) ans 0 for ai, bi in courses: add min(r - ai, need) ans add * bi need - add if need 0: break out.append(str(ans)) print(\n.join(out)) if __name__ __main__: solve()贪心的正确性这里多说一句这不是那种“看起来差不多”的贪心而是可以严格证明的。因为每门课提高分数的单位成本是固定的且在达到满分之前可以任意增量购买所以要让总成本最小必然是按单位成本从小到大依次购买。你可以把它理解成“分数版”的分数背包问题只不过每件物品可以拆成 1 分 1 分地买。踩坑重点有两个第一个是排序方向。按 b[i] 从小到大排也就是把“性价比高”的课程放前面。我见过有人按 a[i] 排序或者按 r - a[i] 排序那都是不对的。第二个是循环里 add min(r - ai, need) 的 min 不能漏否则会把某门课提高到超过满分答案就会偏大。最后注意 n * avg 可能很大建议用 64 位整数。2.4 路灯排序后答案藏在三个距离里最后一个题是路灯一条长度为 l 的街道有 n 个路灯位置是 pos[i]路灯的照明半径是 d问最小的 d 是多少才能让整条街道都被照亮。先把路灯位置排序。排序之后问题就变得很清晰了。三类限制决定了 d 的下限第一街道起点 0 必须被照亮。离起点最近的路灯是 pos[0]所以 d 至少是 pos[0]。第二街道终点 l 必须被照亮。离终点最近的路灯是 pos[-1]所以 d 至少是 l - pos[-1]。第三相邻两个路灯之间的空白区域必须被照亮。如果两个路灯的位置分别是 pos[i] 和 pos[i1]那么它们之间的空白长度为 pos[i1] - pos[i]这两个灯各负责一半所以 d 至少是 (pos[i1] - pos[i]) / 2。最终的答案就是这三类距离的最大值。import sys def solve(): data sys.stdin.read().strip().split() if not data: return idx 0 out [] while idx len(data): n int(data[idx]); idx 1 l int(data[idx]); idx 1 pos [] for _ in range(n): pos.append(int(data[idx])); idx 1 pos.sort() ans max(pos[0], l - pos[-1]) for i in range(1, n): ans max(ans, (pos[i] - pos[i - 1]) / 2.0) out.append(f{ans:.2f}) print(\n.join(out)) if __name__ __main__: solve()这道题看起来简单但能踩的坑不少。最常见的两个一是忘记处理两端只算了相邻距离的一半二是相邻距离没有除以 2直接把整段距离当成半径。如果你把这两个坑都躲开了这道题基本就是送分题。另外注意输出格式题目一般要求保留两位小数用 f{ans:.2f} 格式化不要手写四舍五入的逻辑。3. 完整可运行的参考代码与验证过程3.1 如何用 Python 快速跑通所有题目上面我给的代码都是可以独立运行的。这里说一下输入处理的通用模板。牛客笔试的输入往往有多组测试用例但不会显式告诉你组数最常见的方式是“读取到文件末尾”也就是 EOF。用 sys.stdin.read() 一次性读取所有数据然后用一个 idx 指针按顺序解析是最省心的方式。这个模板的好处有三个第一你不用关心输入到底有几行反正按顺序取第二解析速度快不会像 input() 逐行读那样在高数据量下拖后腿第三代码结构统一不容易漏读。3.2 用样例验证输出为了让你看得更清楚我把每道题的样例跑一遍。小易的升级之路输入2 5 3 2解析出来是 n2a5怪物战斗力是 3 和 2。第一个怪物战斗力 3 小于等于 5打掉能力变成 8第二个怪物战斗力 2 小于等于 8打掉能力变成 10。输出 10。瞌睡输入6 3 1 3 5 2 5 4 1 1 0 1 0 0清醒时刻的基础收益是 a[0]a[1]a[3] 132 6。然后找长度为 3 的窗口窗口 [2,4] 的额外收益最大覆盖的是下标 2 的 5 和下标 4 的 5额外收益是 10。最终答案 16。奖学金输入3 100 80 70 10 50 20 80 5当前总分 200目标总分 240还差 40 分。按每提高 1 分需要的时间排序80 分的课成本是 5先提高 20 分到满分花 100 小时70 分的课成本是 10再提高 20 分到 90花 200 小时。总时间 300这时平均分正好 80。输出 300。路灯输入2 15 5 10排序后路灯在 5 和 10。d 至少覆盖起点5至少覆盖终点15-105相邻距离的一半(10-5)/22.5。最大值是 5输出 5.00。这四组样例都可以直接粘贴到代码里验证结果和我写的一致。3.3 从 Python 移植到 C 的注意事项如果你笔试允许选 Python 那当然好但有些公司默认用 C所以我还是提醒几个移植要点。输入输出方面建议用 scanf/printf或者关掉 C 流同步后使用 cin/cout。数据范围方面能力值、总分差、最终答案都可能超过 2^31-1用 long long。浮点输出方面路灯题用 printf(%.2lf\n, ans)不要用 float用 double。C 写小易的升级之路核心循环就是while (n--) { long long x; scanf(%lld, x); if (x a) a x; }奖学金的多组数据处理记得在循环内初始化 total、need、ans不然很容易带着上一组的数据继续算。4. 我刷这套题时踩过的坑与排查技巧4.1 输入处理的坑我见过最多的问题不是算法不会而是多组输入处理不对。有些同学用 input() 一行一行读遇到第一行数据读完后以为结束了结果下一组测试数据读不到直接报错。解决办法就是用 sys.stdin.read() 一次读完再用指针切分。这种“流式解析”的思路在校招笔试里非常实用尤其是题目不说有几组数据的时候。另外一个细节是 read() 读完可能是空字符串记得先 strip()否则 split() 会返回空列表循环直接跳过。4.2 数据范围和溢出小易的升级之路里怪物战斗力可能叠加到很大奖学金里 n * avg 也可能很大。用 int 存这些值的后果是本地样例正常一提交 WA或者出现负数完全看不出来哪里错了。排查方法很简单把所有可能累加的变量都改成 64 位整数。在 Python 里没这个问题但我还是建议你养成习惯凡是涉及总和、乘积、累计优先考虑数据范围。4.3 滑动窗口边界初始化瞌睡这题窗口边界错了很难查。初始化 extra 的时候要算前 k 个元素循环从 k 开始到 n-1先加新元素再删旧元素。顺序不能反反了会重复计算或者漏算。我提供一个自查方法拿一个很小的 n 和 k比如 n3, k2手动在纸上把窗口滑一遍对着代码验证每一步的额外收益。滑动窗口这种题边界不出错的最快方式就是先用小数据手动模拟一遍。4.4 贪心排序方向错误奖学金这题排序方向错了会得到完全错误的答案。我见过有同学按当前成绩 a[i] 排序想着“先把成绩低的补上去”听起来好像有道理但成本不同这么做就不对。比如一门课 90 分提高 1 分需要 100 小时另一门课 30 分提高 1 分只需要 1 小时按成绩排序会先补 90 分那门明显不合理。遇到贪心题先别急着写排序先问自己排序的关键指标是什么这里的指标是“把总分提高 1 分需要付出多少小时”所以要按 b[i] 排序。如果题目没有 b[i] 这个成本所有课提高 1 分的时间都一样才不需要排序。4.5 路灯浮点精度与输出格式路灯这题的输出要求保留两位小数直接 printf(%.2f) 即可。常见的问题是有人把相邻距离除以 2 之后存成 float然后又拿去和 int 比较这时候 C 会做隐式转换结果可能不对。我建议在整个计算过程中统一用 double。另外如果答案本来就是整数比如两端距离是 5输出也应该写成 5.00不要输出 5格式不对照样判错。下面把这几类问题整理成一张排查速查表现象可能原因解决办法升级之路输出异常负数int 溢出改 long long / long瞌睡额外收益偏大或偏小窗口初始化或滑动顺序错误先手动模拟小数据奖学金答案明显过大排序方向错误或漏了 min 上限按成本排序加 min 限制路灯答案少了端点覆盖没算 pos[0] 和 l-pos[-1]三类限制都取最大值输出格式不对没保留两位小数用 printf(%.2f) 或 f-string5. 刷完这套题之后下一步往哪走5.1 从这套题看大厂笔试的出题逻辑很多同学刷题有个误区总觉得笔试会考特别偏的算法于是花大量时间堆冷门知识点。实际上绝大多数大厂的校招笔试前面的题目难度就是网易2016这套题的级别重点考察的是你能否把题目描述翻译成代码逻辑能否在边界条件下保持正确能否在时间复杂度上不犯低级错误。说到底笔试筛掉的不是“不会难题的人”而是“连简单题都写不稳的人”。这套题的价值就在于帮你把基础盘打扎实让你在真正笔试时看到同类题目能快速建立思路。5.2 每个考点对应的进阶题目刷完这套题如果你想继续深挖每个考点都有对应的进阶题可以去练。模拟题的进阶方向是“大模拟”比如螺旋矩阵、旋转数组、Z 字形变换这类题不考算法考的是代码组织能力和细心程度。滑动窗口的进阶方向是无重复最长子串、最小覆盖子串这两道题是面试高频。贪心的进阶方向是区间调度、跳跃游戏核心还是那个问题每一步的最优选择是什么这个选择会不会影响后面的选择。边界处理的进阶方向是二分查找的各种变体你会发现很多二分题不是死在算法上而是死在 left、right、mid 的边界更新上。5.3 给校招同学的刷题节奏建议我个人建议的节奏是先把这套网易2016题独立做一遍不要看题解哪怕花一整天也要自己写出来。不会的题标记好过两天再独立写一遍。这样两遍下来你对“模拟、滑动窗口、贪心、边界处理”这四类基本能力会有一个很踏实的掌握。之后再去刷更系统的题单比如按公司分类的真题、按算法分类的题单、按难度递进的热题 100 题。每一道题做完之后都想一个问题这道题和之前做过的哪道题在思路上是相通的这种“归因”训练比盲目刷题效率高得多。我在实际刷题中最深的体会是笔试很多时候拼的不是灵光一闪而是稳定输出。像这套题里的路灯、奖学金思路都不难但真正能在 20 分钟内把边界全部处理对、一次提交通过的人其实没有想象中那么多。你不要追求刷题数量有多吓人先把这类基础题做到“闭着眼都不会错”后面再碰复杂题心态会完全不一样。
