P5718这道题我在给新人讲循环和数组的时候几乎必讲。它来自洛谷“深入基础”题单第4章的例2题目短得离谱核心诉求只有一个——输入 n 个数输出最小值。很多同学十分钟写完交上去就 AC 了转头就忘。但我每次讲完都会让大家在这个题上多停一会儿因为这道题看起来简单却是从“会写循环”跨到“用循环解决一个抽象问题”的关键台阶后面那些最小值、最大值、求和、计数甚至再往后的贪心、动态规划追根溯源都能回到这道题的思维模式上。这篇博客就把 P5718 从题目拆解、思路推导、代码实现到常见错误完整过一遍最后再给出几个同类型的变式练习思路。无论你是刚摸键盘的初学者还是正在带新人的老手应该都能从里面捞到点有用的东西。1. 题目本身在说什么先把输入输出和边界条件盘清楚1.1 题目信息提取原题面不长翻译成大白话就是先读入一个正整数 n接着读入一行 n 个整数最后把这 n 个数里的最小值单独输出一行。输入格式大概是这样的第一行一个正整数 n表示整数的个数第二行n 个整数两两之间用空格隔开输出格式只有一行一个整数表示这 n 个数中的最小值。数据范围按“深基”题单早期的风格给得相当宽松n 通常在 1000 以内读入的整数在 int 范围内。这个宽松的范围很重要后面讲代码的时候我会专门说到它对做题策略的影响。1.2 自己构造一个样例走一遍流程不用原题样例我们随手编一组数据就能把流程跑通。输入5 8 3 9 1 7人工扫一遍8、3、9、1、7最小的是 1。所以预期输出是 1。这个例子看着简单但它包含了一个很多初学者没意识到的点当数据量小的时候“人眼扫描”可以瞬间给出答案但当数据量到几千、几万个甚至从文件流或网络流里源源不断进来时程序必须有一个明确的、一步一步执行的规则来处理数据。这个规则就是算法。1.3 “深基4”这个位置为什么值得注意P5718 挂着“深基4.例2”的前缀这个编号本身就说明了它在学习路径里的位置。它处在一个人刚学完分支结构、刚接触循环结构和数组概念的阶段算是从“语句能不能写对”过渡到“逻辑能不能理清”的第一批题。我见过不少学习者看到这题的第一反应是这题目有什么好讲的不就是 min 函数一下吗这种想法恰恰忽略了它真正的教学意图。深基系列把这个题放在这么靠前的位置不是让你调一个现成函数输出答案而是让你理解“最值”这个概念在程序里是怎么被一步一步计算出来的。理解了这一层后面学排序、学二分、学贪心你都比别人多了一层底层的直觉。2. 从“排序取第一个”到“一次遍历维护最优”思路是怎么一步步收敛的2.1 新手最常想到的笨办法排序很多刚学了 sort 的同学拿到这题第一反应是把所有数排个序然后输出第一个不就行了代码甚至只要两行sort(a, a n); cout a[0] endl;我承认在这道题的数据范围下这个做法也能 AC。但我强烈不建议你养成这个习惯。原因很简单排序的输出信息量远大于“最小值”这个单一信息。排序把 n 个元素的完整顺序全部算出来了而你只需要其中最小的那一个这相当于你为了买一瓶酱油把整个超市都盘了一遍库存。复杂度上对比更直观排序是 O(n log n)而一次遍历求最小值是 O(n)。当 n 只有 1000 的时候log n 很小两者跑起来都是毫秒级差距可以忽略。但等后面刷到 n 10^6 的题O(n log n) 和 O(n) 可能就是“压线过”和“稳稳过”的区别。更关键的是思维方向一个只会用排序求最值的人在遇到不能排序的流式数据时会直接卡住。2.2 最朴素也最优雅的解法让一个变量永远记住当前最小的数正确的思路其实非常朴素。你不需要把整个数组都排好序只需要准备一个变量姑且叫它 minn让它从头到尾记录“到目前为止我看到的最小值”。过程是这样的先读入第一个数把它放进 minn。然后依次读入后面的每一个数 x。每次读完拿 x 和 minn 比较如果 x 比 minn 小就把 minn 更新成 x。所有数处理完minn 里装的就是整个序列的最小值。为什么最后 minn 一定是全局最小值这里可以做一个非常简单的归纳论证。处理完第一个数后minn 是“已处理序列”的最小值这显然成立。假设处理完前 k 个数后minn 是前 k 个数的最小值。现在处理第 k1 个数 x如果 x 小于 minn说明前 k1 个数的最小值是 x于是更新 minn如果 x 大于等于 minn说明前 k 个数里那个最小值依然是整体最小值minn 不变。两种情况下处理完前 k1 个数后 minn 仍然代表已处理序列的最小值。把这个过程一直推到 n结论就出来了。这个证明思路本身也是计算机科学里非常重要的一种思想——循环不变式。很多算法正确性的证明都要靠它。你在这道题里第一次接触它远比你想象的有价值。2.3 “边读边比”意味着什么不需要把数据全部存下来这道题还有一个很容易被忽略的进阶点因为最小值只和“当前看到过的数”有关和后面还没读到的数没有任何关系所以我们根本不需要先把所有数存进数组再从头遍历一遍。换句话说这题有两种写法第一种先开数组把 n 个数全部读进去然后遍历数组找最小值。第二种不存数组读一个数就立刻比较、立刻更新全程只用一个变量。第二种写法在内存上是 O(1) 的不管 n 是一千、一万还是一个亿它都只占一个变量的空间。这个特性放到真实场景里非常重要比如你在处理一个持续产生的传感器数据流时你不可能先把所有数据存下来再算最值必须在数据到来的一瞬间完成判断。所以“边读边比”不是一个奇技淫巧而是流式处理思想的雏形。我带的不少学生第一次意识到“原来不存数组也能算最值”时眼睛会亮一下那一刻才是真正把这道题吃透了。3. 代码实现C 和 Python 各写一遍每个细节都说明白3.1 C 数组版稳妥、直观、适合入门先给出最容易理解、也最贴合“数组”章节教学目标的版本#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } int minn a[0]; for (int i 1; i n; i) { if (a[i] minn) { minn a[i]; } } cout minn endl; return 0; }逐行解释一下。vectorint a(n)声明了一个能装 n 个 int 的动态数组这种方式比int a[1005]更安全因为它会根据 n 的实际大小分配内存不会出现“数组开小了越界”或者“数组开大了浪费”的问题。第一个 for 循环负责读入数据。然后关键的一步是int minn a[0]先把第一个元素作为当前最小值这样初始化能保证 minn 一开始就在数据范围内不会出现用 0 初始化导致全正数序列答案错误的情况。第二个 for 循环从下标 1 开始逐个和 minn 比较并更新。3.2 C 边读边比版空间 O(1)竞赛里更推荐接下来是“不存数组”的版本我实际做题时更常用这个#include bits/stdc.h using namespace std; int main() { int n; cin n; int minn; cin minn; // 第一个数直接作为初始最小值 for (int i 1; i n; i) { int x; cin x; if (x minn) { minn x; } } cout minn endl; return 0; }这个版本的好处是少了一个数组变量内存占用更小而且代码逻辑更贴近“数据不断到来”的真实场景。要注意的是它假设 n 至少是 1。题目确实保证了 n ≥ 1所以没问题但如果你在自己写测试时传入 n 0这个代码会直接读入失败这一点心里有数就行。顺便说一个 C 输入的小细节如果用 cin 做题建议在 main 函数开头加上ios::sync_with_stdio(false);和cin.tie(0);这两行能显著加快 cin 的读取速度。在 n ≤ 1000 的时候不写也无所谓但养成习惯之后遇到大规模输入就不会莫名其妙地超时。3.3 Python 实现自己写循环不要只依赖 min 函数Python 里最偷懒的写法当然是print(min(a))一行解决。但如果是奔着练算法去的我建议你还是老老实实写一遍循环n int(input()) a list(map(int, input().split())) minn a[0] for x in a[1:]: if x minn: minn x print(minn)如果不存数组Python 也可以这样n int(input()) nums map(int, input().split()) minn None for x in nums: if minn is None or x minn: minn x print(minn)这里用minn None配合minn is None判断是为了让代码在 n 为任意非负整数时都健壮。实际做题时 n 保证为正你也可以直接读第一个数初始化。Python 版的核心逻辑和 C 完全一致理解了一份另一份就是换层皮的事。3.4 三种常见的 minn 初始化方案对比把初始化方案单独拿出来对比是因为这是这道题以及所有“最值类”题目最大的坑点。初始化方案写法示例优点缺点用第一个数minn a[0]初始化值一定在数据范围内逻辑最稳需要保证数组非空题目已保证 n ≥ 1用极大值minn INT_MAX或const int INF 1e9第一个数一定会触发更新适合流式读取若数据可能超过这个值需要把 INF 调大用 0 或其他常数minn 0写法最简单数据全为正数时答案恒错数据全为负数时也会错最不推荐我见过无数人在这个坑里翻车尤其是刚学完数组、自己写个小测试时样例恰好有 0 或有负数结果 AC 不了还找不到原因。所以送大家一句话初始化最小值要么用第一个元素要么用一个“大到不可能超过”的值绝对不要拍脑袋写 0。4. 实战中我最常看到的报错和排查思路WA、RE和编译问题逐个过4.1 答案错误样例过了但提交 WA八成是初始化问题有位读者之前给我发过一段代码逻辑写得完全正确但是输出的答案永远是 0。我一看他的初始化写的是int minn 0;。如果题目的数据范围全是正整数那么每个数都不小于 0if (a[i] minn)永远不成立minn 永远停留在 0答案自然就是 0。这种错误的可怕之处在于如果样例里恰好有一个数小于 0你本地测出来的结果是完全正确的提交上去就 WA。因为在线评测的测试数据往往包含各种边界情况比如全是正数的情况、全是负数的情况你的代码在某一类数据上就会暴露问题。排查方法很简单本地测试时故意构造几组“极端数据”所有数都是正数如5 1 2 3 4 5所有数都是负数如5 -1 -2 -3 -4 -5所有数都相同如5 7 7 7 7 7只有一个数如1 100这几组数据一跑初始化问题立刻现出原形。4.2 运行错误数组越界和大数组开在栈里的隐患RERuntime Error在这道题里相对少见但也不是没有。最常见的 RE 是数组越界。比如你开了int a[100]但题目数据 n 可能是 200读入时a[i]直接越界程序崩溃。解决方法是养成用vector的习惯或者先看清楚题目给的数据范围再开数组。还有一种 RE 隐患不那么显眼在 main 函数内部开了一个特别大的静态数组。比如int main() { int a[1000000]; ... }在 Windows 上局部变量通常放在调用栈中栈空间一般只有 1MB 到 8MB一个int a[1000000]就是 4MB可能直接爆栈。虽然这道题 n ≤ 1000 不会触发但以后刷到大数据量的题就危险了。解决办法是把大数组放到 main 函数外面作为全局变量全局变量存在数据段里空间大得多。4.3 编译错误骚操作越多越容易花式 CE编译错误Compile Error通常是提交时语言选错了或者本地用着某个编译器特有语法、换到评测机就不认识了。举例来说有些同学在本地用 VS 写代码用了scanf_s提交到洛谷的 GCC 环境里直接编译失败因为scanf_s是 Windows 特有的。所以竞赛提交前把代码里的_s后缀去掉。还有一个经典问题#include bits/stdc.h这个万能头文件本地能编译是因为你的编译器支持但个别评测环境如果不支持就会 CE。洛谷是支持这个万能头文件的这一点不用担心但如果你换到其他 OJ 上就要谨慎。稳妥的写法是明确包含需要的头文件比如iostream、algorithm、vector。4.4 输出格式的严格性换行和空格其实有讲究多数 OJ 对行末空格不敏感但“要不要输出换行”一般是宽容的有些题不输出换行也能 AC。不过我建议永远在输出末尾补一个endl或者\n一是符合题目描述二是如果你后面用管道把输出接到别的程序里没有换行可能会出现奇怪的拼接。这里还有个小技巧endl会额外做一次刷新缓冲区的操作在输出量大的时候比\n慢。这题的输出就一行用哪个都一样但以后刷高输出量题目时建议直接写cout minn \n;。4.5 一个很多人忽略的边界n 1 时到底会不会出错我之前让一个新同学讲讲他的代码在 n 1 时怎么跑他支支吾吾半天说不出来。实际上用“先读 a[0]循环从 i 1 开始”的写法n 1 时循环一次都不执行直接输出 a[0]这是正确的。但如果你把循环写成了for (int i 0; i n; i)n 1 时会访问 a[1]数组越界结果未定义。这也是一个通用的做题习惯每次写完代码第一件事就是看边界条件。对于这道题n 1 是最小的合法输入单独测它n 等于最大值也要测。把边界数据全部跑通正确率会提升一大截。5. 从这道题出发一类“扫描维护”问题的通用打法与进阶练习5.1 五种常见的变体核心逻辑几乎不用改把这道题吃透之后下面这些变体其实只是改几个符号的问题变体题目核心改动一句话思路找最大值if (x minn)改成if (x maxx)维护当前最大值同时找最大值和最小值同时维护 minn 和 maxx一次遍历两个变量找最小值出现的位置在更新 minn 的同时记录下标第一次出现就更新之后相等不更新得到第一次位置找第二小的值维护 min1 和 min2 两个变量遇到比 min1 小的先让 min2 接住 min1求平均值维护一个 sum 累加变量遍历结束后 sum / n以“找最小值第一次出现的位置”为例代码是这样int minn a[0]; int pos 0; for (int i 1; i n; i) { if (a[i] minn) { minn a[i]; pos i; } } cout pos endl; // 注意下标从 0 开始题目要求输出第几个时记得 1这里有个细节是如果要求“最后一次出现的位置”就把if (a[i] minn)改成if (a[i] minn)这样相等时也会更新位置遍历结束后 pos 存的就是最后一次出现的位置。这个“小于”和“小于等于”的区别在不少题目里都是决定成败的关键。5.2 再往后走这种“维护最优”的思路通向哪里“一次遍历 维护状态变量”是整个算法学习里出现频率最高的一种模式。举几个例子前缀和遍历时维护sum x你就能在 O(1) 时间内查询任意区间和。滑动窗口在遍历中维护窗口内的最大值或最小值典型题目是滑动窗口最大值。贪心算法很多贪心题的核心就是在遍历中维护“当前能拿到的最优选择”。动态规划滚动数组优化的本质也是只保留上一阶段的少数几个状态而不是全部状态。所以P5718 真正教给你的不是“怎么输出最小值”而是“在数据流动的过程中如何用有限的状态压缩信息”。这个思想一旦建立后面的很多算法对你来说就不再是孤立的知识点而是一棵树上的不同分支。5.3 我的一个建议练习序列连着刷几道同源题巩固手感学完之后别急着做新题型先把同一思路的题连着刷几道形成肌肉记忆。以洛谷的“深入基础”题单为例你可以按这个顺序练P5718 找最小值本文讲的题先做到能不看代码完整写出来。P5719 分类求平均数遍历中同时维护多个变量练习“一次扫描解决多个统计需求”。找第二小值或第 k 小值先不要上排序尝试用维护变量或堆的思路做。带位置的最值问题输出最大值和它第一次出现的位置练习下标同步更新。这些题做下来你对“循环里维护状态”的理解会非常扎实后面看到一个新题第一反应会是“我需要维护哪些状态”而不是“我要怎么套模板”。5.4 最后分享一个我常用的自查方法做完任何一道题我都建议用一组“极端小数据 极端大数据 随机数据”自查。极端小数据就是 n 1 或 n 2极端大数据就是卡着题目上限构造随机数据则可以在本地写一个小脚本生成。把它们全部跑一遍对照预期输出没问题了再提交。这个习惯我坚持了好几年它帮我拦下了大量低级失误也让我的 AC 率一直保持在比较高的水平。P5718 只是一个起点但这个自查习惯你在下一道、下下道题里会受益无穷。