1. 项目概述从一道JOI预选题看算法竞赛中的“购物”思维最近在带学生备赛信奥信息学奥林匹克和准备一些算法面试时我重新翻看了JOI2024预选赛的题目。其中P14293这道“购物2”Shopping 2让我觉得特别有意思。它不像一些纯考数据结构的题那样直接也不像一些数学题那样烧脑而是非常典型地考察了选手将实际问题抽象为算法模型并选择合适策略进行优化的能力。说白了这就是在考你“会不会买东西”——当然是用程序员的思维去买。题目的大意是你有N种商品要买每种商品有一个价格。商店正在进行“K元优惠”活动具体规则是你可以选择任意一段连续的商品序列子数组如果这段序列中商品的价格总和大于等于K那么你就可以为整段序列支付总价 - K的费用相当于立减K元。你只能使用一次这个优惠。现在需要你计算在最优地使用或不用这次优惠的情况下购买所有商品的最小总花费是多少。刚拿到题可能有的同学会想这不就是求所有子数组的和然后判断是否大于等于K再计算优惠后的价格最后取最小值吗这个思路完全正确也是这道题最直接的暴力解法时间复杂度是O(N²)。但JOI的题目N的规模往往在10^5级别O(N²)显然会超时。所以这道题的核心就从“怎么做”变成了“如何高效地做”。它要求我们在O(N log N)甚至O(N)的时间内找到那个能让总花费最小化的最优优惠区间。这背后涉及的是对前缀和、单调性以及双指针尺取法等基础但至关重要的算法工具的熟练运用。接下来我就结合这道题拆解一下这类“区间选择优化”问题的通用解题框架和我在实战中总结的一些技巧。2. 核心思路解析为什么暴力不行以及如何优化2.1 问题重述与暴力解法首先让我们把问题用数学语言更清晰地定义一下这是解题的第一步。设商品价格数组为A[1..N]。 设所有商品的总价为total_sum sum(A[1..N])。 设优惠券的门槛值为K。我们的目标是选择一个区间[l, r](1 ≤ l ≤ r ≤ N)使得花费最小。 花费的计算公式为cost total_sum - discount其中discount折扣额的计算方式是如果区间[l, r]的和sum(l, r) K那么discount K否则discount 0。因此总花费可以写成cost total_sum - (sum(l, r) K ? K : 0)由于total_sum是固定值要让cost最小实际上就是要让discount最大。而discount要么是K要么是0。所以问题的本质转化为是否存在一个区间其和大于等于K如果存在我们就能获得K的折扣此时最小花费就是total_sum - K如果不存在那么最小花费就是total_sum即原价购买。等等那岂不是太简单了只要遍历所有区间找到一个和≥K的区间答案就是total_sum - K这里有一个关键的陷阱题目要求的是购买所有商品的最小总花费。使用优惠券时你只是对选中的区间[l, r]支付sum(l, r) - K而对于区间外的商品你仍然需要支付它们的原价。所以总花费的公式应该是总花费 (区间外商品总价) (区间内商品总价 - K) 如果区间和≥K (total_sum - sum(l, r)) (sum(l, r) - K) total_sum - K你看化简之后结果确实是total_sum - K并且与所选的具体区间[l, r]无关只要它的和≥K。这个化简过程非常精彩它揭示了本题的第一个核心洞察只要存在任何一个和≥K的区间使用优惠券就一定比不用更划算并且最终花费是固定的total_sum - K。那么暴力解法就清晰了计算total_sum。遍历所有可能的区间[l, r]计算其和sum(l, r)。如果存在某个sum(l, r) K则输出total_sum - K否则输出total_sum。这个算法的时间复杂度是 O(N²)对于 N 最大为 2×10^5 的数据范围计算量高达 4×10^10必然超时。2.2 优化关键从O(N²)到O(N)的思维跃迁既然暴力枚举所有区间不行我们必须寻找更高效的方法来判断“是否存在一个和≥K的区间”。这实际上是一个经典的“子数组和”问题。一个常用的优化技巧是使用前缀和。定义prefix[i] A[1] A[2] ... A[i]那么区间[l, r]的和可以快速计算为prefix[r] - prefix[l-1]。我们的目标就变成了是否存在一对下标(l, r)满足prefix[r] - prefix[l-1] K其中1 l r N。转换一下不等式prefix[r] K prefix[l-1]。对于固定的r我们需要判断是否存在一个l满足l r使得prefix[l-1] prefix[r] - K。换句话说我们需要在prefix[0]到prefix[r-1]中注意l-1的范围是0到r-1找到一个最小值min_prefix然后检查是否满足prefix[r] - min_prefix K。为什么找最小值因为如果连最小的prefix[l-1]都能满足prefix[r] - min_prefix K那么对于其他更大的prefix[l-1]这个不等式更成立。这利用了前缀和的单调性不一定严格单调但找最小值这个操作是合理的。于是算法可以优化为计算前缀和数组prefix其中prefix[0] 0。初始化min_prefix 0因为prefix[0] 0。从左到右遍历r从 1 到 N a. 计算当前区间和的下界current_sum prefix[r] - min_prefix。 b. 如果current_sum K那么我们就找到了一个满足条件的区间可以立即得出结论存在并输出total_sum - K。 c. 更新min_prefix min(min_prefix, prefix[r])为下一个r做准备。这个算法只需要一次遍历时间复杂度是 O(N)完美解决了大规模数据的问题。空间复杂度是 O(1)因为我们只需要维护一个min_prefix和当前的prefix_r可以边读入边计算无需保存整个数组。注意这里有一个非常关键的细节就是min_prefix的初始化和更新时机。min_prefix必须在判断之后更新。因为对于当前的r我们寻找的l必须满足l r即l-1 r-1。所以用来计算current_sum的min_prefix必须是prefix[0..r-1]中的最小值。如果我们先更新min_prefix用prefix[r]去更新再判断那就相当于允许了l r1的情况这显然是不合法的区间。这个顺序是很多初学者容易出错的地方。2.3 算法实现框架与边界处理基于以上的分析我们可以给出清晰的算法步骤和C实现框架。算法步骤读入 N 和 K。初始化total_sum 0,prefix_sum 0,min_prefix 0,found false。prefix_sum是动态计算的前缀和相当于prefix[r]。min_prefix是prefix[0..r-1]的最小值。循环读入 N 个商品价格price a.total_sum price。 b.prefix_sum price。 // 此时prefix_sum是prefix[r]c. 判断如果prefix_sum - min_prefix K则设置found true并可以提前结束循环因为已经找到答案。 d. 更新min_prefix min(min_prefix, prefix_sum)。 // 为下一个r准备根据found输出结果如果found为真输出total_sum - K。如果found为假输出total_sum。边界情况考虑K0根据题意如果区间和≥0则可以使用优惠。任何区间都满足所以答案一定是total_sum - 0 total_sum。我们的算法也能正确处理因为prefix_sum - min_prefix 0恒成立min_prefix是历史前缀和最小值可能为负吗商品价格是非负整数前缀和单调不减min_prefix就是prefix[0]0所以差值为非负条件成立。所有商品价格之和小于K显然不存在任何区间和≥K算法会遍历完所有商品found为假输出total_sum。N1算法依然有效第一次循环就会判断单个商品是否≥K。3. C代码实现与逐行解读理解了算法代码实现就水到渠成了。这里我给出一个清晰、高效且带有详细注释的C实现。#include iostream #include algorithm // 用于 min 函数 using namespace std; int main() { // 关闭同步提升大规模数据读入速度这是竞赛常用技巧 ios::sync_with_stdio(false); cin.tie(nullptr); int N; long long K; // 注意K的范围可能很大用long long cin N K; long long total_sum 0; // 所有商品总价 long long prefix_sum 0; // 当前前缀和即 prefix[r] long long min_prefix 0; // prefix[0..r-1] 的最小值初始为 prefix[0]0 bool found false; // 标记是否找到满足条件的区间 for (int i 0; i N; i) { long long price; cin price; total_sum price; // 步骤1: 更新当前前缀和 prefix_sum price; // 现在 prefix_sum 代表 prefix[r] // 步骤2: 判断以当前i为结尾的区间是否存在和K // 即判断 prefix[r] - min(prefix[0..r-1]) K // 此时的 min_prefix 存储的就是 min(prefix[0..r-1]) if (prefix_sum - min_prefix K) { found true; // 找到后可以提前结束但需要读完本行输入不可以直接break。 // 但为了代码清晰和避免后续输入混乱这里选择设置标志位继续读完或break。 // 在竞赛中因为找到答案后后续计算无关紧要可以直接break以节省时间。 // break; // 可以选择直接跳出循环 } // 步骤3: 更新 min_prefix 为 prefix[0..r] 的最小值供下一个i使用 // 注意更新必须在判断之后确保min_prefix代表的是r之前的历史最小值 min_prefix min(min_prefix, prefix_sum); } // 输出结果 if (found) { cout total_sum - K endl; } else { cout total_sum endl; } return 0; }代码关键点解读数据类型选择题目虽未明确给出价格和K的上限但根据JOI题目的惯例和防止溢出考虑使用long long是更稳妥的做法。int在极端情况下如所有价格都很大N也很大可能会溢出。输入输出优化ios::sync_with_stdio(false);和cin.tie(nullptr);是C竞赛代码的标配。它们解除了C标准流与C标准流的同步并解除了cin与cout的绑定可以大幅提升输入输出效率在面对大量数据时效果显著。核心逻辑循环prefix_sum动态维护相当于我们算法描述中的prefix[r]。if (prefix_sum - min_prefix K)这行代码是整个算法的灵魂。它检查了以当前下标i为区间右端点r时是否存在一个左端点l由min_prefix对应的历史位置隐含使得区间和≥K。min_prefix min(min_prefix, prefix_sum);这行代码在判断之后执行保证了min_prefix始终是“过去”的最小值符合l r的要求。提前终止在发现found true后我们可以直接break跳出循环因为答案已经确定。这里为了演示的完整性我让循环继续执行完毕。在实际竞赛中使用break是更优的可以节省不必要的读入和计算时间。但需要注意如果提前break后续的商品价格将不会被读入total_sum也就不完整了。因此如果选择break必须在循环外使用另一个循环或方法跳过剩余的输入或者重新计算total_sum。一个更简洁的做法是在找到答案后继续读入但不处理或者简单累加到total_sum因为输出只依赖于found和total_sum。但既然找到了total_sum - K就是答案后续价格不影响结果。所以直接break并输出total_sum - K是安全的前提是total_sum在break前已经累计了所有已读入商品的价格。在我们的代码逻辑中total_sum的累加发生在循环开头如果break在累加之后、判断之前那么total_sum是包含当前商品价格的没问题。但为了绝对稳妥和代码清晰示例中使用了found标记。4. 算法正确性证明与复杂度分析4.1 为什么这个贪心策略是正确的有些同学可能会疑惑我们一直在维护min_prefix并只用它来判断这会不会漏掉一些情况比如是否存在一个区间[l, r]其和≥K但是prefix[r] - min(prefix[0..r-1])却小于K我们来证明一下。假设存在一个满足条件的区间[l, r]即S prefix[r] - prefix[l-1] K。根据定义min(prefix[0..r-1])是prefix[0]到prefix[r-1]这些数中的最小值。那么一定有min(prefix[0..r-1]) prefix[l-1]。将这个不等式两边同乘以-1并加上prefix[r]得到prefix[r] - min(prefix[0..r-1]) prefix[r] - prefix[l-1] S K。所以如果区间[l, r]满足条件那么prefix[r] - min(prefix[0..r-1])也一定满足条件。反之如果对于某个r有prefix[r] - min(prefix[0..r-1]) K那么我们就找到了一个具体的区间左端点l就是使得prefix[l-1]等于那个min(prefix[0..r-1])的索引l注意可能有多个位置等于最小值取任何一个都行。这个区间[l, r]的和就是prefix[r] - min(prefix[0..r-1]) K。因此我们的算法“检查是否存在r使得prefix[r] - min(prefix[0..r-1]) K”与“检查是否存在区间[l, r]使得其和≥K”是完全等价的。算法没有遗漏任何可能的情况。4.2 时间与空间复杂度时间复杂度我们只对数组进行了一次线性扫描。在扫描过程中每个元素被读入一次进行常数次算术运算和比较操作累加、减法、比较、取最小值。因此总的时间复杂度是O(N)。空间复杂度我们只使用了几个固定数量的long long型变量和一个bool变量来存储中间状态没有使用任何与N成比例的数组除了输入缓冲区。因此空间复杂度是O(1)。这是一个非常优雅的原地算法。对比暴力O(N²)的算法O(N)的算法在N200,000时运算次数大约是20万次而O(N²)则是400亿次效率天壤之别。这也正是算法竞赛的魅力所在——通过巧妙的思维将不可能变为可能。5. 常见错误与调试技巧在实际实现和调试这道题时我见过学生们踩过不少坑。这里总结几个最常见的错误1min_prefix更新时机错误这是最经典的错误。如前面所述如果先更新min_prefix再判断代码可能如下min_prefix min(min_prefix, prefix_sum); // 错误先更新了 if (prefix_sum - min_prefix K) { // 此时min_prefix可能包含了prefix_sum本身 found true; }这样会导致判断时min_prefix可能等于当前的prefix_sum如果它比历史值都小那么prefix_sum - min_prefix 0从而可能漏掉一些有效的区间特别是当区间就是单个元素且其值≥K时。务必记住判断用的是“历史”最小值更新是为“未来”做准备。错误2整数溢出题目没有明确给出数字范围但商品数量和单价都可能很大。如果使用int类型来存储total_sum,prefix_sum,K在累加或比较时很容易溢出导致结果错误甚至程序运行异常。在信奥竞赛中对于涉及求和、累积的问题只要数据范围没有明确说明很小无脑使用long long通常是安全的选择。错误3忽略K0的情况虽然我们的算法能正确处理K0但有些同学的思路可能不同。例如有人可能会想“区间和必须严格大于0才能优惠”那就错了。题目条件是 K所以K0时任意区间都满足折扣就是0总价不变。我们的算法中min_prefix初始为0prefix_sum - 0 0恒成立价格非负所以会立即找到并输出total_sum - 0结果是正确的。错误4输入输出效率在本地测试时数据量小感觉不到差别。但提交到在线评测系统OJ面对大量测试数据低效的I/O会成为性能瓶颈。务必养成使用ios::sync_with_stdio(false); cin.tie(nullptr);的习惯。同时对于C使用cin/cout而不是scanf/printf时这两行代码至关重要。调试技巧小数据测试自己构造一些小的测试用例包括边界情况。N1, price KN1, price KN2, 价格组合各种情况都小于K和大于K但单个小于K等等K0K非常大大于所有商品总和打印中间变量在怀疑逻辑出错时可以在循环内打印prefix_sum,min_prefix,prefix_sum - min_prefix的值观察其变化是否符合预期。对比暴力算法写一个O(N²)的暴力程序用于对小规模随机数据N100进行对拍。生成随机数据分别运行你的优化程序和暴力程序比较输出结果是否一致。这是竞赛中验证算法正确性非常有效的方法。6. 举一反三同类问题与扩展思考P14293这道题的本质是“判断是否存在子数组和大于等于给定值K”。这是一个非常基础且重要的模型可以衍生出许多变体问题。变体1寻找和大于等于K的最短子数组长度如果问题变成求一个和≥K的连续子数组的最小长度。我们的算法可以很容易地扩展。在维护min_prefix的同时我们还需要记录取得这个最小前缀和时的下标索引min_index。当prefix[r] - min_prefix K时我们就找到了一个以r结尾的、满足条件的区间其长度为r - min_index。我们只需要在所有满足条件的r中取这个长度的最小值即可。这依然可以在O(N)时间内完成。变体2寻找和小于等于K的最大子数组和思路类似我们可能需要维护一个“最大前缀和”的单调队列或者使用二分查找。核心还是利用前缀和将区间和问题转化为两个前缀和之差的问题。变体3商品价格有正有负本题假设价格是非负的所以前缀和数组是非递减的min_prefix就是prefix[0]问题退化为简单的遍历。但如果价格可以是负数前缀和就不再单调。此时要判断是否存在和≥K的区间我们上面的算法依然有效因为我们的算法并不依赖前缀和的单调性它正确维护了prefix[0..r-1]的最小值。这是一个很强的性质。但是如果要求最短长度等情况会复杂一些可能需要借助数据结构如平衡树或线段树来维护前缀和的有序性以便进行二分查找。扩展思考双指针尺取法的适用性有些同学可能会想到用双指针。双指针尺取法通常适用于寻找“和恰好等于K”或“和小于等于K”的最长/最短区间并且要求数组元素都是正数。对于本题“和≥K”如果数组元素都是正数双指针也是可行的移动右指针扩大和当和≥K时记录并尝试移动左指针缩小区间同时更新最小长度如果是求长度。但我们的前缀和最小值维护的方法更通用不要求元素为正且代码非常简洁。通过这道JOI预选题我们不仅学会了一个具体的O(N)算法更重要的是掌握了“前缀和转化”和“维护历史极值以加速当前判断”这一强大的思维工具。在解决诸如最大子数组和、区间和满足某种条件的区间查找等问题时这个工具会反复出现。下次遇到类似问题不妨先想想能不能计算前缀和能不能通过维护某个历史信息最小值、最大值、索引等来避免内层循环