洛谷 B4450 / B3867 / B3923 智慧购物、储蓄与做题——从程序到生活

洛谷 B4450 / B3867 / B3923 智慧购物、储蓄与做题——从程序到生活 摘要B4450 用数组追踪每种文具的最低价B3867 用数组累加每个储蓄罐的存款B3923 用三变量滚动模拟斐波那契式做题计划并设终止条件。三道题都以小杨的日常生活为背景——购物、存钱、学习——恰好覆盖了最常见的三类应用需求比价、记账、计划。三道题共享一个数据结构——数组——分别用作最小值追踪器、“累加器和滚动窗口”。本文从伪代码题解出发延伸到这些算法模式如何变成真实应用比价网站淘宝/京东的最低价筛选、记账软件支付宝/微信账单、习惯养成 App——你在洛谷上写的a[k]p和ans[a]i在工业界是比价引擎和个人金融系统的核心逻辑。题目链接B4450 小杨的智慧购物 | B3867 小杨的储蓄 | B3923 小杨做题 目录 前言 三道题在考什么 B4450小杨的智慧购物 思路 伪代码 关键点 B3867小杨的储蓄 思路 伪代码 关键点 B3923小杨做题 思路 伪代码 关键点⚖️ 三题对比⚠️ 注意事项 延伸从程序到生活——算法模式如何变成应用 比价与最低价追踪 累加器模式记账与储蓄 斐波那契式增长习惯与复利 数组——从考试题到数据库 三道题的现实映射 延伸阅读文献 前言这篇题解没有源代码只有伪代码。作为一名信奥教练我不提倡复制粘贴。我见过太多学生搜到题解、复制、粘贴、提交、AC——代码跑通了脑子没跑通。下次遇到变体题还是不会。伪代码剥掉了语言的壳只留算法的骨架。你看不到#include看不到cin、cout看不到那些让你以为我会了的语法细节。你能看到的只有这一步做什么、下一步做什么、为什么这么做。如果你是路过的友友已经在这道题上挣扎了很久——先去喝杯水回来重新看看自己卡在哪一步。是没读懂题意是思路方向偏了还是代码有 bug 但逻辑其实对大多数时候不是不会是走偏了。偏了不可怕可怕的是偏了之后直接放弃去抄一份能 AC 的代码。抄完你以为你懂了其实你只是搬了别人的结论。除非你时间真的紧张——比赛临近、作业要交——那种情况先 AC 再说能理解。但平时练习给自己一点耐心。先自己想、自己写、自己调跑不过了再来看伪代码你的思路和这里差在哪一步。那一步就是你真正学到的东西。 三道题在考什么三道题都以小杨的日常生活为背景但考察的算法模式截然不同B4450 智慧购物B3867 储蓄B3923 做题生活场景买文具找最低价每天往储蓄罐存钱按斐波那契式计划做题数组用途最小值追踪器累加器—三变量滚动核心操作a[k]min(a[k],p)ans[a]ia,b,sum三变量递推算法模式分组取最小分组累加递推 提前终止现实对应比价网站记账软件习惯养成 AppB4450 用数组下标当种类编号数组值存该种类的最低价——每来一件新商品比较并更新。B3867 用数组下标当储蓄罐编号数组值存该罐的总金额——每来一天把天号等于金额累加进去。B3923 不用数组用三个变量滚动模拟斐波那契式序列到达阈值就停。三道题对应了三种最基本的程序模式选择取最小、累积加起来、递推用前项算后项。这三种模式覆盖了日常生活中 80% 的计算需求。 B4450小杨的智慧购物 B4450 思路M 种文具N 件商品。对每件商品种类 k价格 p更新种类 k 的最低价。最后把 M 个种类的最低价加起来。数组a[k]用种类编号 k 做下标存该种类目前的最低价。初始化为 0表示还没见过该种类。读入一件商品时如果a[k]0第一次见设为 p如果a[k]p更便宜更新为 p。 B4450 伪代码读取 M, N 数组 a[1..M] 初始化为 0 // a[k] 种类 k 的最低价 对 i 1 到 N: 读取 k, p 如果 a[k] 0: // 第一次见到这个种类 a[k] p 如果 a[k] p: // 比已知的更便宜 a[k] p 总价 0 对 k 1 到 M: 总价 a[k] // 每种种类的最低价求和 输出 总价 B4450 关键点数组下标 种类编号。这是数组最强大的用法之一——用下标直接索引到对应类别O(1) 查找和更新。不需要遍历搜索。a[k]0的首次判断。初始值为 0 表示未见过。第一次遇到种类 k 时a[k]0设为 p。之后只做a[k]p的比较。因为价格 ≥10 永远不会被误认为有效价格。用样例追踪输入a[1]a[2]说明1 110种类1首次价格11 21021不更新1 1101不1不更新2 313种类2首次价格32 1013103不更新总价 a[1]a[2] 13 4。分组取最小模式。这道题的本质是把 N 件商品按种类分组每组取最小值再求和。在数据处理中这是GROUP BY MIN SUM的模式——SQL 里的一行聚合查询。 B3867小杨的储蓄 B3867 思路N 个储蓄罐编号 0 到 N-1。第 i 天往储蓄罐 a_i 里存 i 元。D 天后输出每个储蓄罐的总金额。数组ans[a]用储蓄罐编号做下标每来一天把天号 i等于存入金额累加进去。 B3867 伪代码读取 N, D 数组 ans[0..N-1] 初始化为 0 // ans[j] 储蓄罐 j 的总金额 对 i 1 到 D: // 第 i 天 读取 a // 今天选的储蓄罐编号 ans[a] i // 存入 i 元天号 金额 对 j 0 到 N-1: 输出 ans[j]后跟空格 B3867 关键点累加器模式。ans[a] i一行代码完成了找到对应储蓄罐和累加金额两个操作。数组下标直接定位储蓄罐不需要搜索。用样例 1 追踪N2, D3, 选择序列 [0,1,0]天 i储蓄罐 a操作ans[0]ans[1]10ans[0] 11021ans[1] 21230ans[0] 342输出4 2。天号 金额。第 i 天存 i 元——题目把天数和金额巧妙地绑定在一起。ans[a] i中的i既是循环计数器又是存入金额一行代码两个用途。0 号编号。储蓄罐从 0 开始编号不是 1。输出也从 0 号开始。这是 C/C 的习惯——数组下标从 0 开始。 B3923小杨做题 B3923 思路第 1 天做 a 题第 2 天做 b 题第 3 天起每天 前两天之和斐波那契式。如果某天做了 ≥ m 题之后不再做题。求 N 天内总共做了多少题。用三个变量a前前天、b前天、sum今天滚动递推。每天做完后检查b m是否满足终止条件。 B3923 伪代码读取 a, b, m, N total 0 sum 0 对 i 1 到 N: 如果 i 1: sum a // 第1天 total a 否则如果 i 2: sum sum b // 第2天sum 此时 a b total b 否则: // 第3天起 a b // 滚动前前天 原前天 b sum // 滚动前天 原今天 sum a b // 今天 前前天 前天 total b // 累加今天做的题数 如果 b m: // 达到阈值停止 跳出循环 输出 total B3923 关键点三变量滚动。斐波那契式序列只需要前两项不需要存整个序列。用a、b、sum三个变量滚动——每次迭代把b传给a、sum传给b、新值传给sum。空间 O(1)。用样例 1 追踪a1, b2, m10, N5天 ia(前前)b(前)sum(今)做的题totalb≥m?112111210212323210323536310435851151055813819810输出19。序列 1, 2, 3, 5, 8 是斐波那契式每项 前两项之和。提前终止。样例 2a1, b1, m5, N8第 5 天做了 5 题 ≥ m5break。total1123512。N8 但只做了 5 天——break跳出循环后面的天不做也不加。b m的检查时机。检查在每天做完之后——当天做到 ≥m 题仍然算入 total但从第二天起不做题。如果题目改成做到 ≥m 题当天就不算检查要移到累加之前。 两个建议修复的隐患。原始代码有两个依赖碰巧才正确的写法建议显式修复隐患原始代码问题建议修复sum未初始化int sum;局部变量不初始化值未定义。碰巧为 0 才正确int sum 0;第 1 天用sum a;依赖sum初始为 0。如果sum有垃圾值结果错sum a;设值不是累加修复后的第 1-2 天逻辑如果 i 1: sum a // 设值不是累加 total a 否则如果 i 2: sum a b // 直接算 ab不依赖上一步 total b为什么原代码碰巧能过因为大多数编译器在非优化模式下把未初始化的局部变量零初始化sum碰巧为 0所以sum a等价于sum 0 a a。但这是未定义行为——C 标准不保证未初始化变量为 0。换一个编译器或开优化可能就错了。考试能过不代表代码正确。⚖️ 三题对比B4450 智慧购物B3867 储蓄B3923 做题数组用途最小值追踪累加器不用数组三变量滚动核心操作a[k] min(a[k], p)ans[a] isum a b滚动算法模式分组取最小分组累加递推 提前终止数组大小O(M)O(N)O(1)时间复杂度O(N)O(D)O(min(N, 终止天))生活场景购物比价存钱记账学习计划现实对应比价网站记账软件习惯养成 AppB4450 和 B3867 都用数组做分组——一个按下标分组取最小一个按下标分组累加。B3923 不需要分组只需要递推。三种模式覆盖了日常计算的三种基本需求选择最优、累积总量、预测趋势。⚠️ 注意事项B4450 的a[k]0判断用 0 表示未见过因为价格 ≥1。如果价格可能为 0需要换一个哨兵值如 -1 或INT_MAX。B4450 的long longM≤10⁵每个最低价≤10³总价最多 10⁸——int能存上限约 2×10⁹但用long long更安全。B3867 的 0 号编号储蓄罐从 0 开始输出也从 0 号开始。如果习惯从 1 开始编号容易搞错。B3923 的sum未初始化原始代码中sum声明后未赋初值依赖编译器零初始化。虽然实际能过但这是未定义行为——建议显式初始化sum 0。B3923 的sum avssum a第一行用而非依赖sum初始为 0。如果sum有垃圾值结果就错了。第一行应该是sum a设值不是sum a累加。B3923 的终止条件位置if(b m) break在循环体末尾——当天做的题仍然算入 total从下一天起停止。如果题意是当天达到 m 就不算需要调整位置。 延伸从程序到生活——算法模式如何变成应用你说这三道题从程序到生活到贴近生活让日常更为便捷的应用需求的出现。没错——三道题的算法模式分别对应了三种最常见的日常应用比价、记账、计划。你在洛谷上写的几行代码在工业界是真实产品的核心逻辑。 比价与最低价追踪B4450 的a[k] min(a[k], p)做的事是对每个商品类别追踪最低价。这正是比价网站的核心算法。应用做什么和 B4450 的对应淘宝/京东价格筛选用户选价格从低到高对每类商品显示最低价a[k] min(a[k], p)什么值得买跨平台比价追踪历史最低价a[k]存历史最低新价格来了比较Google Shopping跨商家比价按类别分组GROUP BY 类别 MIN(价格)航旅纵横/携程最低票价对每条航线追踪最低票价a[航线] min(a[航线], 当前票价)B4450 的数据规模是 N10⁵O(N) 一趟扫完。真实比价网站的数据规模是 N10⁸全国商品用同样的算法但加了分布式存储和缓存。算法不变规模变了一千倍。比价网站的技术栈爬虫抓取商品数据 → 按类别分组存入数据库a[k]变成了数据库表的一行→ 查询时取每类最低价SELECT MIN(price) FROM products GROUP BY category→ 前端展示。你在 B4450 里用一个 for 循环做的事比价网站用一条 SQL 查询做同样的事。 累加器模式记账与储蓄B3867 的ans[a] i做的事是对每个储蓄罐累加每次存入的金额。这是记账软件的核心模式。应用做什么和 B3867 的对应支付宝/微信账单按类别餐饮/交通/购物累加支出ans[类别] 金额银行系统按账户累加存取款ans[账户号] 交易额家庭记账 App按成员/类别/月份分组累加ans[维度] 金额健身 App按日期/运动类型累加卡路里ans[日期] 消耗量B3867 中天号 金额的设定在记账软件里变成了时间戳 交易时间金额 交易额——两者解耦了但累加逻辑一样account[target] amount。记账软件的技术栈用户记录每笔交易 → 按维度类别/日期/账户分组累加 → 生成报表。你在 B3867 里用ans[a] i一行做的事记账软件用数据库的SUM(amount) GROUP BY category做同样的事。 斐波那契式增长习惯与复利B3923 的做题计划是斐波那契式增长——每天做的题数是前两天之和。这种用前项推后项的模式在生活规划中无处不在。应用做什么和 B3923 的对应习惯养成 App如 Streaks逐日递增的习惯强度达到目标后维持递推 终止条件学习计划工具每天复习量按遗忘曲线递推艾宾浩斯曲线类似递推理财复利计算每年收益 本金 × (1利率)递推 N 年total total * (1r)健身计划渐进超负荷每周重量 上周 增量递推式增长B3923 的斐波那契式增长在现实中不常见没人真能每天做前一天 前前天量的题但递推 终止的模式是所有计划类应用的底层逻辑从初始状态出发按规则推进达到阈值就停。番茄钟、背单词 App、健身记录器——都在做同样的事一个循环每步更新状态检查终止条件。你在 B3923 里写的forbreak在习惯养成 App 里是while (未达成目标)更新进度。 数组——从考试题到数据库三道题中 B4450 和 B3867 都用数组做分组。这不是巧合——数组是所有数据处理的基础结构。洛谷题数组下标数组值数据库对应B4450种类编号最低价SELECT MIN(price) FROM products GROUP BY categoryB3867储蓄罐编号总金额SELECT SUM(amount) FROM transactions GROUP BY accountB3923—三变量—不需要数据库单行递推数组下标 数据库的 GROUP BY 键。数组值 数据库的聚合结果MIN/SUM。你在洛谷上用a[k]做的事数据库用GROUP BY做——只是数据库帮你封装了循环和查找。数组操作C 代码SQL 对应分组取最小if(a[k]p) a[k]pMIN(price) ... GROUP BY k分组累加ans[a] iSUM(amount) ... GROUP BY a遍历求和sum a[i]SUM(a[i])数组的本质是什么是一个按下标直接定位的存储结构。数据库的索引做了同样的事——用 B 树把按键查找从 O(N) 优化到 O(log N)。你在 B4450 里用a[k]直接定位种类 k 的最低价数据库用索引直接定位某个键的记录——思路一样实现不同。 三道题的现实映射把三道题和延伸放在一起洛谷题算法模式生活场景真实应用技术栈B4450分组取最小购物比价淘宝/什么值得买爬虫 数据库 SQL GROUP BYB3867分组累加存钱记账支付宝账单/银行系统交易流水 SUM GROUP BYB3923递推 终止学习计划习惯养成 App/番茄钟状态机 while 循环三道题覆盖了日常应用的三种核心计算需求选择最优比价、累积总量记账、预测趋势计划。你在洛谷上写的a[k]min(a[k],p)、ans[a]i、sumab在工业界分别变成了比价引擎、记账核心、计划调度器。算法不变封装变了——从for循环变成了 SQL 查询和 API 调用但核心逻辑一脉相承。你今天在洛谷上帮小杨做的事——买最便宜的文具、算储蓄罐里有多少钱、按计划做题——和淘宝帮你比价、支付宝帮你记账、Streaks 帮你养成习惯做的是同一件事用程序让生活更便捷。 延伸阅读文献论文与技术文档E. F. Codd.A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, 1970. —— 关系数据库的奠基论文GROUP BY MIN/SUM 的理论基础。D. E. Knuth.The Art of Computer Programming, Vol. 1: Fundamental Algorithms(3rd Edition). Addison-Wesley, 1997. —— 数组、链表等基础数据结构的权威论述。在线资源洛谷.B4450 [GESP202512 三级] 小杨的智慧购物. https://www.luogu.com.cn/problem/B4450洛谷.B3867 [GESP202309 三级] 小杨的储蓄. https://www.luogu.com.cn/problem/B3867洛谷.B3923 [GESP202312 二级] 小杨做题. https://www.luogu.com.cn/problem/B3923SQL GROUP BY Tutorial — W3Schools. https://www.w3schools.com/sql/sql_groupby.asp —— SQL GROUP BY MIN/SUM 聚合教程。Fibonacci Sequence — Math is Fun. https://www.mathsisfun.com/numbers/fibonacci-sequence.html —— 斐波那契序列入门。Database Indexing — GeeksforGeeks. https://www.geeksforgeeks.org/database-indexing/ —— 数据库索引原理B 树与数组下标的关系。价格比较网站 — 维基百科. Price Comparison Service — Wikipedia —— 比价网站的工作原理与历史。Personal Finance Software — Wikipedia. Personal Finance Software — Wikipedia —— 个人记账软件的发展史。推荐教材T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein.Introduction to Algorithms(4th Edition). MIT Press, 2022. —— 算法圣经含数组、递推、聚合等基础内容。H. Garcia-Molina, J. Ullman, J. Widom.Database Systems: The Complete Book(2nd Edition). Pearson, 2008. —— 数据库系统教材含 GROUP BY、索引、聚合查询。R. Bird.Thinking Functionally with Haskell. Cambridge University Press, 2014. —— 函数式编程视角的递推与累加帮助理解算法模式的抽象。本文标签#算法 #数组 #分组取最小 #累加器 #斐波那契 #比价 #记账 #习惯养成 #洛谷题解 #信奥 #C #入门本文首发于CSDN作者HugoStudio_SWAN