从数列到贪心：算法竞赛基础题的三类常见坑解析-北京尧图网络

这几天整理手头的刷题笔记看到有一套小题目让我印象很深题名干脆利落数列1、修理牛棚、按要求输出序列。乍看都是入门难度但把它们放在一起研究会发现问题往往不只在“会不会算法”更多是出在读题、建模和输出这三件事上。这套题特别适合刚接触算法竞赛、正在刷基础题的读者也适合很久没碰代码、想把信息学手感捡回来的朋友。下面我就按这三个题目展开把思路推导、代码实现和现场容易踩的坑一次性说清楚。1. 数列1这台送分题为什么总有人卡在“输出”上1.1 先把题干翻译成可执行的序列规则“数列1”这类题目的套路可以说是入门第一课题目给你一个序列的定义方式可能给前几项也可能给递推式或通项公式然后让你输出前 n 项或第 n 项。难倒大多数人的不是找规律而是把题干的文字描述准确翻译成循环代码。做这类题我建议先做三件事。第一确认题目要输出的是“前 n 项”还是“第 n 项”前者通常用循环输出后者可以只算一个变量。第二确认数列下标从 1 开始还是从 0 开始很多人在这种地方犯低级错误。第三确认数值范围n 一旦到几十万斐波那契类的结果很快超过 int必须用 long long 甚至取模。举个例子假设题目要求输出前 n 项通项公式是 a_i i^2 - i 1。这个规则很简单但代码里最容易出错的是乘法溢出。如果直接写i * i在 n 较大时 int 会先溢出再赋值结果就错了。常见的写法是先把 i 转成 long long或者用1LL * i * i强制提升类型。1.2 演示一份可以直接跑的数列生成代码对于“数列1”这种题我的实现习惯是单函数解决尽量不加多余逻辑#include bits/stdc.h using namespace std; int main() { int n; cin n; for (int i 1; i n; i) { long long val 1LL * i * i - i 1; cout val (i n ? \n : ); } return 0; }代码本身没什么好讲的关键点在于(i n ? \n : )。这个 ternary 表达式保证了行尾没有多余空格也保证了最后一定有换行。很多测评系统对行尾空格并不敏感但有些严格比对所以写成这种格式永远是最保险的。再扩展一点如果题目给的是递推式比如 a_1 1a_2 1a_i a_{i-1} a_{i-2}那处理方式也类似只是需要一个数组或两个滚动变量。数组写起来更直观滚动变量更省内存对于普通入门题数组完全够用。真正重要的是把公式写在循环里并且保证边界项 a_1、a_2 能正确初始化。1.3 为什么“数列1”这种题还值得写一篇复盘有人会觉得这种题很简单不值得花时间。但实战中我见过不少人在这种题上翻车主要翻在三个地方一是没看清输出项数少输出一项或多输出一项二是数据类型没用 long long大样例直接爆掉三是换行和空格处理得随随便便结果本地看起来没问题提交就是 WA。所以“数列1”这种题真正考察的是读题的严谨性和输出习惯。入门阶段把这两件事练好后面做复杂题会省很多排查时间。你可以把这类题当成一种“格式化输出基本功”它的价值不在算法而在让代码风格从一开始就规范起来。2. 按要求输出序列先把输出规则从题干里完整抄出来2.1 输出规则比算法更值得逐字读“按要求输出序列”这个标题听上去很泛实际指一类特别常见的任务输入一个 n按某种规则输出一个序列或者输出一个二维结构比如三角形、矩阵、螺旋线。题目本身可能很简单但输出格式一旦搞错算法再对也是零分。我后来总结了一条经验拿到这种题不要在脑子里直接开始写主逻辑先把输出规则“抄”到草稿纸上。具体来说要看清楚以下这些细节数字之间用空格还是逗号分隔每行末尾允不允许多余空格输出完毕之后是否需要换行如果有多个测试用例每个用例之间是否有空行输出英文、数字还是特殊符号是否要保留小数保留几位十六进制、八进制还是十进制是否需要补前导零。这些细节里最容易被轻视的就是“行尾空格”和“最后换行”。判断标准很简单测评系统一般用文件比较有的忽略行尾空白有的逐字符比较。你没法预判所以干脆按最严格的标准来写行末不输出多余空格整个输出最后一个字符后跟上换行符。2.2 用“first”标记统一处理分隔符处理行内序列分隔符我首选的模式不是判断i n而是用一个 bool 变量记录是否已经输出过第一个元素bool first true; for (int i 1; i n; i) { if (!first) cout ; first false; cout val; } cout \n;这种写法比i n更通用尤其当循环不是从 1 到 n 的时候。比如你根据某个条件在循环里筛选输出筛选出的个数不确定用first标记就不会出现多一个空格或少一个空格的问题。同理如果题目要求输出用逗号分隔只需要把cout 改成cout ,逻辑完全不变。在 Python 里更省事直接print( .join(map(str, arr)))就保证不会有多余空格。但需要注意join 要求列表元素都是字符串所以要先 map 成 str。用 C 时没有这么方便的函数所以first标记是最稳定的写法。2.3 二维输出的换行和空行陷阱除了普通序列很多题要求按矩阵格式输出。这里常见的问题是“空行位置”。比如两个矩阵测试样例之间要有一个空行而最后一个样例后面不能跟空行。很多初学者会在每个样例结束后都输出空行结果末尾多了一个空行被判 Presentation Error 或 Wrong Answer。处理方式通常是给每个测试用例的结果用一个变量控制判断当前是不是第一个用例只有非第一个用例才在输出前先补一个空行。这样最后一个用例结束后不会多出空行。这种“前缀空行”的思路比“后缀空行”要稳妥得多。下面这个表是我现在做输出题之前必查的清单建议你也抄一份检查项常见错误推荐做法数字分隔符句末多空格用 first 标记或条件判断行尾换行最后一组没有换行统一在输出后追加\n多组样例空行末尾多空行用“前缀空行”模式数据类型大数溢出先算乘法再看范围格式类型该用十六进制用了十进制逐字抄下题目要求大小写Hex 输出成 hex复制样例别手打3. 修理牛棚从零推演贪心断板法3.1 这个经典问题到底在求什么“修理牛棚”是信息学里非常有名的贪心题你会在很多公开题目和练习册里见到它的变体。题目大意是有一排牛棚门被暴风雨打坏了棚里有牛的 C 个位置编号可能不连续。现在最多能用 M 块木板去修门每块木板可以覆盖任意长度的一段连续牛棚。要求用这些木板覆盖住所有有牛的牛棚同时让木板总长度最小求这个最小总长度。这个问题的第一反应很容易是数位 DP 或动态规划因为 M 和位置都有限制DP 也能做。但贪心解法更简短也更体现思维含量。核心是把“增加一块木板”理解成“在原有连续覆盖范围里切开一个空隙”。如果只有一块木板那必须从最左边有牛的牛棚一直盖到最右边有牛的牛棚总长度就是最后一个位置 - 第一个位置 1。比如位置是 2、8、15、30、42、50一块木板要覆盖 2 到 50长度是 49。这个长度当然很大因为中间很多牛棚没有牛也被一并盖上了。如果有两块木板就可以在某一处“断开”。断开的位置应该选在没有牛的连续空隙里。每断开一个空隙被木板覆盖到的牛棚总数就会减少一个空隙长度。所以想让木板总长度最小就是要选出一些尽可能大的空隙不被木板覆盖。3.2 贪心策略为什么是选最大空隙继续把问题抽象原本是一整段连续覆盖现在最多增加 M 块木板意味着最多可以有 M-1 个断点也就最多可以选择 M-1 个空隙“省掉”。省掉的空隙越多木板总长度越小。因此策略很简单给所有有牛牛棚的位置排序计算相邻有牛位置之间的空隙长度把空隙按长度从大到小排序优先选择最长的那 M-1 个空隙从总跨度中减去。这里会有一个疑问为什么相邻有牛位置之间的空隙长度是pos[i] - pos[i-1] - 1因为如果两个有牛位置分别是 15 和 30那么中间没有牛的牛棚是 16 到 29一共 30 - 15 - 1 14 个。这 14 个位置如果能断开不盖木板总长就减少 14。贪心正确性的逻辑也很直白每一次增加一块木板都是选择当前最大的空隙来省掉。前面选择的大空隙不会影响后续选择其它空隙的收益所以每一步的局部最优组合起来就是全局最优。这就是典型的“排序取最大”型贪心。我用一组位置数据来手算一遍位置 2、8、15、30、42、50假设 M 3。首先排好序总跨度 50 - 2 1 49。相邻空隙分别是2 和 8 之间58 和 15 之间615 和 30 之间1430 和 42 之间1142 和 50 之间7从大到小排序是 14、11、7、6、5。因为最多用 3 块木板最多选择 2 个空隙选 14 和 11得到答案 49 - 14 - 11 24。用三块木板实际分配一下木板 1 盖 2 到 15长度 14木板 2 只盖 30 这一个牛棚长度 1木板 3 盖 42 到 50长度 9。三块加起来正好 24同时所有有牛位置都被覆盖到了。这个结果非常符合直觉最长的两个空隙被省掉了木板总长度自然最小。3.3 修理牛棚的完整参考代码#include bits/stdc.h using namespace std; int main() { int M, S, C; cin M S C; vectorint pos(C); for (int i 0; i C; i) { cin pos[i]; } sort(pos.begin(), pos.end()); int ans pos.back() - pos.front() 1; vectorint gaps; for (int i 1; i C; i) { int gap pos[i] - pos[i - 1] - 1; if (gap 0) gaps.push_back(gap); } sort(gaps.rbegin(), gaps.rend()); for (int i 0; i M - 1 i (int)gaps.size(); i) { ans - gaps[i]; } cout ans \n; return 0; }代码里有三处细节值得说。一是sort(pos.begin(), pos.end())题目输入可能不按顺序必须排序。二是gap 0才入数组因为相邻位置相等这种情况虽然实际输入里很少见但加了判断代码更稳。三是循环条件里i M - 1 i (int)gaps.size()这保证即使 M 很大、空隙不够多也不会越界。还有一个很容易被忽略的情况当 M C 时每头牛用一个单独的长度 1 木板就好总长度就是 C。上面的代码会自动处理这种情况吗会。因为这时能减去的空隙数量受gaps.size()限制最多把 C-1 个空隙全部减掉最后ans刚好等于 C。输入里 C 可能等于 1此时gaps为空ans就是 1也没有任何问题。4. 实测中真正容易翻车的边界三个问题一起复盘4.1 边界条件和数据范围优先单独测试把这三道题放在一起刷最大的收获是“边界条件几乎决定成败”。很多选手样例过了就直接交结果正式数据一来就 WA原因往往不是主算法错了而是某个边界情况没处理。数列题要注意 n 等于 1 或 n 等于 0 的情况。n 等于 1 时循环只跑一次输出一个数就好但别忘了换行。n 等于 0 时严格来说不应该有输出有些题目保证 n 0但如果不保证就应该加一句判断直接返回。修理牛棚要注意 M 非常大和 C 非常小的情况。比如 M 50C 1这时候只需要一块长度为 1 的木板。如果代码里对pos.back()和pos.front()做运算C 1 时这两个值相同ans 1后面的循环也不会执行结果正确。再比如 C 3位置是 1、2、3M 2。这时总跨度是 3唯一空隙是位置 2 和 3 之间其实位置是连续的空隙长度为 0。排序后没有实际空隙可以选择最终 ans 还是 3因为两块木板没有必要分开直接一块长度 3 就能解决问题。4.2 走查法比反复提交更高效我现在调试这类基础题的习惯是“走查法”写完代码不急着提交先去把题目给出的样例手工模拟一遍再设计几个极端样例。所谓走查就是拿着笔和样例数据一行一行地按代码逻辑在纸上执行看输出是否和预期一致。比如修理牛棚这道题我会主动构造这几个测试输入中牛棚位置没有排序比如 50、2、30检查排序是否生效M 非常大比如 M 100C 5检查答案是否等于 C所有牛都集中在连续位置比如 1、2、3答案是否不受木板数量影响答案会很大检查 int 和 long long 是否够用。构造完极端用例再跑一遍基本能排除 90% 的边界问题。这个方法看着笨但比起反复提交试错效率高得多也更能培养对代码的掌控感。4.3 输出问题要当成独立知识点练习前面说的输出格式看起来是小问题但实际考试里影响很大。我的习惯是准备一个小模板嵌套到所有题目里去for (int i 0; i n; i) { if (i ! 0) cout ; cout arr[i]; } cout \n;这个模板没有用i n - 1来做判断而是用if (i ! 0)哪怕循环内逻辑复杂它也能保证中间有空格、末尾不空格。写矩阵输出时我再套一层“前缀空行”的处理逻辑多组样例之间就不会出现多余空行。把这些输出模式练熟基本可以把输出这块的丢分降到零。5. 顺手复盘三道题暴露的基础能力模型5.1 读题能力、建模能力和输出能力是三条腿把“数列1”、“修理牛棚”、“按要求输出序列”放在一起你会发现它们恰好对应三种基础能力读题、建模、输出。数列题考察能不能把文字规则变成循环修理牛棚考察能不能把真实场景抽象成排序和空隙输出序列题考察能不能把计算结果精确地格式化。这三种能力在复杂题目里会同时出现。与其等到做难题时手忙脚乱不如在入门阶段就把每一条腿都练稳。这也是我对这套小题目评价比较高的原因它没有堆砌复杂算法却逼着你在每一个环节都做到规范。5.2 刷基础题的正确姿势和心态我见过不少学习者刷题只看题解把答案抄一遍就感觉自己会了。但基础题的核心价值不是“知道解法”而是“亲手完成从题意到代码的闭环”。建议每道题做完之后哪怕 AC 了也停留五分钟想三个问题如果数据范围扩大十倍代码还能跑吗如果输出格式改成逗号分隔需要改哪里题目描述换一种场景本题的模型还能套用吗5.3 个人向的小经验我在实际写题过程中感受最深的一点是基础题一定要慢。这不是说做题速度慢而是说不要在思路还没成型时就开始敲键盘。尤其像修理牛棚这类题先把样例数据和公式手算一遍代码写起来就顺很多。还有一个小经验是别急着把bits/stdc.h当成万能药水。在本地用没问题但还是要清楚头文件里包含的东西以及为什么vector能用sort和rbegin()。基础阶段的每一个细节都是在给后面更复杂的题打地基。

从数列到贪心：算法竞赛基础题的三类常见坑解析

相关推荐

COMSOL焓法耦合温度场与流体场的相变模拟实操指南

游戏本地存档重构：从JSON迁移到SQLite的实战指南

游戏存档重构：从JSON到SQLite的实战经验与性能优化指南

更多资讯

Vue智慧水务系统源码拆解：可视化大屏与实时监测实践

artcraft：数字时代的手工艺智能协作范式

智能体能力单元（agent-skills）工程化实践指南

预测性资产维护套件：Intel优化版XGBoost故障概率预测实战

Docker+Jenkins+GitLab：自定义分支自动部署完整指南

diplay：轻量级Python CLI文件结构查看工具

今日更新

声子晶体仿真：三角晶格与六角晶格的能带计算实战

度假村安保定岗定编：岗位梳理、编制测算与排班设计

COMSOL等离子体模块实战：氩气双层DBD仿真建模全解析

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？