洛谷P5726打分题详解：数组遍历、最值筛选与输出精度

洛谷 P5726 这道题题号全称是【深基4.习9】打分不管是我自己当初刷题还是后来带新人入门都把它当数组章节的“体检题”来用。题目本身短得离谱输入 n 个整数评分去掉一个最高分和一个最低分剩下的分数求平均保留两位小数输出。乍一看这题不是有手就行但我在题解区和答疑群里见过太多人在这道题上反复栽跟头——不是思路不会而是精度处理、边界判断、输出格式这些小地方频繁出错AC 不了又找不到原因。这篇文章不打算只贴一份能过的代码而是把这题背后的考点、几种不同思路的取舍、代码实现的细节、常见的坑全部拆开讲清楚。无论你是刚学数组的初学者还是想帮别人讲题的带队老手这篇应该都能给你一些值得参考的东西。1. 这道题到底在考什么1.1 一句话拆解题目需求很多人拿到题就急着写代码其实先花两分钟拆题后面的路会顺畅得多。这个题的核心要求可以拆成四步读入 n 和 n 个整数找到其中的最大值和最小值把它们从总和里剔除用剩余 n-2 个数的和除以 n-2得到平均分。注意题目说的是“去掉一个最高分和一个最低分”不是去掉所有重复的最高分和最低分。比如输入是9 9 8 8 7最高分 9 只去掉一个最低分 7 只去掉一个剩下的是9 8 8和是 25除以 3 约等于 8.33。有同学用排序后pop_back加erase的方式处理逻辑没错但如果写成了“去掉所有等于最大值的数”结果就会不一样。这就是为什么我强调先拆题把“一个”这个量词圈出来后面实现才不会跑偏。另外题目给定评分都是整数但最终平均分可能是小数所以涉及浮点数运算。这里就埋了一个经典的坑用整数除法还是浮点除法我们后面专门讲。1.2 为什么它是数组入门的“分水岭”在“深基4”这个章节里前面的习题大多只需要单个变量加循环就能解决比如求和、计数、找最大值。但【深基4.习9】打分这道题不一样它要求你同时管理一整组数据并且对整组数据做“整体操作”先整体统计再剔除极端值最后汇总计算。这个转变恰好是数组章节的核心价值所在。数组不是用来“存一堆数”的而是让程序能够对一批相关数据做批量处理。这道题虽然简单却把数组最常见的几种用法都覆盖了用下标访问元素、遍历数组统计、记录最值的位置或数值、基于数组内多个元素做聚合计算。可以说这道题就是一块试金石如果你能不看题解独立 AC说明你对数组的基本操作已经比较扎实如果你写起来磕磕绊绊那正好借这个题把基础补一补。从数据结构的角度看这道题也隐含了一个最值筛选的思想。现实中的“评委打分去掉最高最低再平均”本质是剔除离群点、降低极端值对结果的影响这和大数据预处理里的截尾均值Trimmed Mean是一个思路只是在算法题里被简化成了固定去掉一个最值。理解到这层你看到的就不仅仅是一道水题而是一个小型的统计处理模型。2. 解法设计两种主流思路的取舍2.1 思路A排序后掐头去尾最直观先排序让数组从小到大排列。因为要删掉一个最高分和一个最低分排序后最低分在a[0]最高分在a[n-1]直接从下标 1 遍历到 n-2 累计求和即可。#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]; } sort(a.begin(), a.end()); double sum 0; for (int i 1; i n - 1; i) { sum a[i]; } double avg sum / (n - 2); printf(%.2f\n, avg); return 0; }这个思路的好处在哪直观、不容易漏逻辑。你只需要会写sort剩下的就是循环求和思路和题目描述几乎一一对应。很多新手在比赛里紧张写复杂逻辑容易出错用这个解法可以把出错面降到最小。代价是时间复杂度。sort的复杂度是 O(n log n)当 n 很小这道题 n 不超过 1000时完全无所谓。但如果你以后遇到 n 是 10^5 甚至 10^6 的同类问题排序方案就会显得笨重。所以排序法适合作为“保底方案”它永远是对的但不是所有场景下最优的。2.2 思路B一次遍历找最值更接近本质如果你愿意多想一步会发现其实根本不用排序。去掉最高分和最低分本质上只需要知道两个东西最大值是多少、最小值是多少。至于中间那些数谁大谁小跟最终结果一点关系都没有。于是我们可以用一次循环同时完成三件事累加总和、记录最小值、记录最大值。循环结束后用总和减去这两个极值再除以 n-2就是答案。#include iostream #include iomanip #include climits using namespace std; int main() { int n; cin n; int mn INT_MAX; int mx INT_MIN; double sum 0; for (int i 0; i n; i) { int x; cin x; sum x; if (x mn) mn x; if (x mx) mx x; } double avg (sum - mn - mx) / (n - 2); cout fixed setprecision(2) avg endl; return 0; }这段代码的关键在于mn和mx的初始值。如果把mn初始化为 0而分数全为正数那循环里的更新条件x mn永远不成立最小值就一直是 0最后减错。正确的做法是让最小值初始化为一个“大到不可能”的值最大值初始化为一个“小到不可能”的值。通常用INT_MAX和INT_MIN这是我个人比较推荐的方式因为它是标准库定义的、可读性强当然你也可以用1e9和-1e9这种大数硬编码效果一样。时间复杂度是 O(n)空间复杂度是 O(1)因为甚至不需要把整个数组存下来读一个处理一个就行。这种方式和排序法相比在数据量大的场景下优势明显。而且我认为它更接近这道题的“本质”你不需要知道中间的排序只需要抓住极端值。2.3 两种思路的对比与选择建议我用一个表格把两种思路放在一起对比方便你根据场景选择对比维度排序法遍历法代码直观程度高和题目描述几乎一一对应中等需要理解“减极值”的数学含义时间复杂度O(n log n)O(n)空间复杂度O(n) 存数组O(1)边读边处理适用场景新手学习、n较小、后续可能要访问排序结果数据量大、追求效率、逻辑清晰后更推荐出错风险低但排序可能改变原有数据顺序略高主要是初始值设置问题我给新手的建议是第一遍用排序法 AC确保自己能写出完整、正确的代码第二遍再尝试用遍历法实现一次体会如何从“做法”上升到“算法思维”。这两步都走完这道题才算真正吃透。3. 代码实现与精度细节3.1 保留两位小数printf 与 cout 的两种姿势这题要求输出保留两位小数看似简单但我在答疑时见过至少三种翻车写法。第一种是直接cout avg输出的可能是一长串小数比如8.33333直接 WA。第二种是printf(%d, avg)把浮点数按整数输出类型不匹配在部分编译器上结果是错的。第三种是cout setprecision(2) avg少了fixed结果可能是8.3而不是8.30——注意setprecision单独使用是保留两位有效数字而不是两位小数。正确姿势有两个。用printf最省事printf(%.2f\n, avg);用cout则需要同时加fixed和setprecision(2)cout fixed setprecision(2) avg endl;很多初学者不理解fixed的作用我用一句话解释fixed表示“小数点后的固定位数模式”没有它setprecision(2)会被解释成“最多保留两位有效数字”有它才会严格保留两位小数。你可以自己在编译器里分别跑一下cout setprecision(2) 8.0和cout fixed setprecision(2) 8.0输出分别是8和8.00区别一目了然。3.2 整数除法陷阱为什么必须转成浮点数这是本题最隐蔽的坑也是很多人本地跑得好好的、提交却 WA 的原因。看这个例子double avg (sum - mn - mx) / (n - 2);如果sum声明为int那么sum - mn - mx是整数n - 2也是整数C 里整数除以整数得到的是整数除法小数部分直接丢弃。比如23 / 3的结果是7然后赋值给double也只是7.0而不是7.67。正确的做法有两种。一种是把sum直接声明成double这样sum - mn - mx默认就是浮点数除法自动变成浮点除法。另一种是保持sum为int但在计算时显式转换double avg (double)(sum - mn - mx) / (n - 2);我个人的习惯是凡是平均分、比例、百分比这类可能产生小数的结果从一开始就把累加变量声明成double省得后面还要想转换位置。这是写数值计算代码的一个通用经验宁可一开始就用浮点也不要在最后一步才被动转换。3.3 Python 解法参考虽然是洛谷的题目很多同学用的也是 C但 Python 解法同样值得一看因为它的代码更短更容易看出核心逻辑n int(input()) scores list(map(int, input().split())) scores.sort() avg sum(scores[1:-1]) / (n - 2) print(f{avg:.2f})注意两点Python 的f{avg:.2f}会自动做四舍五入这跟 C 的printf(%.2f)行为一致都是“四舍六入五成双”的银行家舍入规则。不过这题的测试点一般不会在这种舍入边界上刁难你所以不用过度担心。另外input().split()如果输入数据跨行也没关系split()会自动把换行符和空格都当作分隔符处理不需要额外拼接逻辑。Python 版本展示了一个很重要的思想代码是给人读的也是给机器跑的。短代码不一定最优但可读性高逻辑一目了然这类题完全可以靠语言特性简化操作。4. 踩坑实录我在这道题上交过的学费4.1 坑一n3 时的边界问题当 n 等于 3 时去掉一个最高分和一个最低分中间只剩一个数这个数本身就是平均值比如1 2 3去掉1和3结果是2.00。排序法和遍历法都能正确处理逻辑上不会出问题。但如果 n 等于 2 呢去掉最高分和最低分后剩下的数是 0 个除以n-20那就是除零错误。这道题的测试数据会避免这种输入但你写代码时要养成一个意识除数至少要是 1。我在实际开发中遇到过类似的业务逻辑——评委人数少于 3 人的评分系统要特殊处理不能直接套公式。算法题虽不考这个边界但这个意识必须建立起来。还有一个相关的小细节如果所有分数都相同比如5 5 5 5去掉一个最高分和一个最低分剩下的仍然都是 5平均值是 5.00。这个场景看着简单但排序法里的“去掉一个”到底去哪个 5有些人会纠结。其实不用纠结因为剩下的全是 5结果一样。这类“重复值”场景可以作为自测用例验证代码是否稳健。4.2 坑二最值初始化的隐蔽错误我在 2.2 里提到过INT_MAX和INT_MIN这里展开讲一个真实案例。某同学用遍历法写这道题把mn初始化为 0提交后一直是 WA。他自己查了半天认为逻辑没问题因为“分数都是 0 到 100 的正数最小值不可能是 0 以下”。但他忽略了一件事当把mn初始化为 0 后循环中的if (x mn)对于所有x 0都不会成立于是mn永远停留在 0。最后计算时减去的“最小值”其实是 0而不是真实的最小分数结果自然错。这个案例后来被我总结成一类典型问题当你要在一组数据里找最小值时初始值必须是一个“比你所有可能遇到的数都要大”的数而不是“看起来合理的 0”。反过来找最大值初始值必须比所有可能值都要小。我把这称为“最值搜索的语义陷阱”严格遵守这个规则能帮你避开一大类 bug。4.3 坑三输出格式被系统误判这道题的输出格式要求是“保留两位小数”但有些同学会把结果输出成8.3或8.333系统直接判 WA。更隐蔽的情况是用printf(%.2lf\n, avg)和printf(%.2f\n, avg)其实在 C 里都可以因为%lf在printf中与%f等价但在scanf中才有区别。有同学把这种写法混用在有些编译器上会有警告虽然不至于报错但为了规范和可移植性建议统一用printf(%.2f\n, avg)。另外如果输出少了换行符某些严格的判题系统也会报错。洛谷一般是 Accept 模式对行尾换行不是特别敏感但养成良好的习惯所有输出以\n结尾。5. 进阶与迁移从这道题还能学什么5.1 同类型题目的解题套路去掉一个最高分一个最低分求平均这个模式可以抽象成更一般的问题从一组数据中剔除若干个最大值和最小值再对剩余数据做统计。如果剔除的数量是固定的 k那思路完全一样只是循环边界变成for (int i k; i n - k; i)除数变成n - 2*k。更进一步如果剔除比例不是整数个而是一个百分比比如去掉两端各 5% 的数据那就需要计算具体剔除多少个这在实际的数据分析里就叫截尾均值。从这个角度延伸你能发现练习题之间的关联。比如有些题目要求求中位数、求方差、求百分位数核心都是“对数组的批量统计”只是统计公式不同。你完全可以把这题的代码模板化读入数组、排序、指定区间求和、除以区间长度。以后遇到类似的统计类题目这个模板可以直接套。5.2 从“能 AC”到“写得漂亮”的三个小习惯这道题 AC 之后我建议你做三件小事把代码质量再提一个台阶。第一把“魔法数字”清理掉。比如100、1000这些题目里的数据范围不要散落在代码各处可以用const int MAXN 1005;定义既提升可读性也避免改数据范围时漏改。第二验证你的代码能处理“最坏情况”。比如 n 取最大值、分数取最大值或最小值用极端数据在本地跑一遍确认没有溢出、没有越界。这道题 n 很小一般不会溢出但养成“构造边界数据自测”的习惯以后做难题会受益匪浅。第三尝试把逻辑封装成函数。比如写成double averageAfterTrim(vectorint scores, int trimCount)把“剔除极值求平均”这个语义抽出来。这样代码结构更清晰以后在其他题目里也能复用。虽然这道题用不着函数但对初学者来说这是一个从“写代码”向“设计代码”迈进的绝佳契机。我在实际带人刷题时发现一个普遍现象很多人在简单题上只追求 ACAC 完就不再看第二眼。但真正拉开差距的恰恰是在简单题上有没有做“额外动作”。把这道题的排序法、遍历法、边界构造、函数封装都过一遍你花的时间可能比直接 AC 多半小时收益却远不止这道题的 100 分。这道题我前前后后写过不下五次每次带新人讲数组都会翻出来。现在回头看它最值得细品的地方不在于算法本身而在于帮你养成“先拆题、再动手、后自测”的做题节奏。如果你刷这道题时正好卡在某个细节上希望这篇文章能帮到你如果已经 AC也不妨按上面的思路再重构一次自己的代码也许会有新的体会。