周五晚上刷到 CF 998 Div.3我的状态是A 题 Fibonacciness 五分钟交掉B 题 Restore the Weather 八分钟也过掉然后卡在 C 题上硬生生磨了二十多分钟。说实话Div3 前几场的 C 题大多是一眼贪心或者简单结论题但 998 这场 C 题给我的感觉完全不一样——题干里套了一层故事样例也没给多少提示一不小心就把自己绕进去。这篇文章就来复盘一下我是怎么把这道“cf 998 div3 c”从读不懂题到 AC 的完整过程包括题意抽象、贪心证明、代码实现和赛后总结。适合刚打 Div3、经常在 C 题卡壳的同学也适合想系统练习“最小操作次数让数组变有序”这类题的选手。1. 为什么 C 题才是 Div3 的“分水岭”1.1 A、B 的套路几乎是固定的先说前面两道热身题因为只有对比才能看出 C 题的位置。A 题 Fibonacciness本质上是个枚举题。题目给了一个长度为 5 的序列中间某个位置是未知的问最多能凑出多少个满足“前两项之和等于后一项”的三元组。我当时直接枚举未知数填什么把几种可能值各算一遍取最大值就过了。这类题的信号很明确数据范围极小选项有限暴力枚举不会出事。B 题 Restore the Weather是一个排序贪心。给一个数组 a 和一个数组 b要求把 b 重新排列成 c使得每个位置都满足 |a[i] - c[i]| k。做法也很机械把 a 的下标按照值排序把 b 也排序然后按顺序匹配。因为排序后两个有序序列对应位置的差是最小化了的所以只要这种匹配都不超过 k其他匹配更不可能更优。这是 Div3 前两题最典型的命题方式——套一个情景但背后的模型一眼就能看穿。这两道题做下来人会处于一种“这把稳了”的放松状态而 C 题正好在这个节点上给你换了一种考法。1.2 C 题开始考“建模”到了 C 题题面变长样例变少而且正确解法往往不是第一直觉想到的那个。A、B 题是“看到模型就做”C 题则是“先把模型从题干里拽出来”这一步会劝退很多人。998 这场 C 题给我的最大冲击是它不像 B 题那样把排序的意图摆在明面上而是把一个数组操作题包在一个看起来像是模拟的故事里。如果你照着字面意思去模拟基本会写挂如果你能看穿它本质上是在问“最小操作次数让一个数组满足某种顺序约束”那这道题的难度其实不高。所以我一直觉得Div3 的比赛里C 题才是真正筛选选手的地方。A、B 考的是熟练度C 考的是抽象能力。2. C 题的题意翻译剥掉故事壳之后就是一个数组模型2.1 题目核心模型很多人卡在 C 题不是因为不会算法而是因为题干里的故事太啰嗦。把题目里的修饰词全删掉最后要你解决的事情其实非常干净给定一个长度为 n 的数组 a一次操作可以选择任意一个下标 i把 a[i] 的值减少 1。问最少需要多少次操作才能让整个数组变成非递减的也就是满足 a[1] a[2] ... a[n]。注意这里每一步只能让某个数减一不能加也不能整体操作。目标不是把数组排成某个给定序列而是让它满足“从左到右不下降”这个性质。如果原题里的数值处理有一些故事背景比如“猎人的战斗力”“城市的防御值”本质上都不影响这个模型。我当天读完题之后第一件事就是在草稿纸上把这个模型写出来——后面的所有思考都建立在它上面。2.2 手算一个完整样例光说模型有点干我拿一个样例手算一遍。设 n 5数组为a [4, 1, 5, 2, 3]目标是把它变成非递减。一眼能看出来最大的麻烦在第三个位置5 后面是 2 和 3它太大了必须降下来。但降到多少合适呢我的处理方式是从右往左看。最后一位 a[5] 3它是整个数组的最右端约束不需要向谁看齐。再看 a[4] 2它比 3 小这没问题而且它反而成为一个新的“更紧的下限”——因为非递减序列里前面的数不能大于它而它只有 2所以前面所有比 2 大的数都必须降到 2 以下。继续往左a[3] 5 比当前的下限 2 大所以它必须降到 2代价是 3。再看 a[2] 1它比 2 更小于是下限继续降到 1。最后 a[1] 4 比下限 1 大降到 1代价是 3。总代价(5 - 2) (4 - 1) 6最终数组可以变成 [1, 1, 2, 2, 3]它满足非递减而且总操作次数是 6。这个结果不是“某个版本的最小值”而是唯一的最优结果因为每一个被降下来的数字都已经压到了它右边所有数字里的最小值没有任何多余操作。2.3 最容易踩的误读我在这个题上浪费了不少时间主要因为三个误读。第一误以为要用“从左往右”的方式贪心。我第一反应是维护上一个位置的值如果当前值比上一个小就把前面一串拉低。实际上这样也能做但你不知道后面还会不会出现更小的数很容易写成一堆区间更新把自己绕晕。倒着扫才是真正的线性做法。第二误以为目标是“让数组变成某个确定的序列”。这个误解很致命。非递减只是一个性质不是某一个固定结果所以很多人会去考虑排序后匹配把问题想复杂了。第三把这题往 DP 上靠。因为看到“最小操作次数”有人会去想状态转移之类的东西。但仔细看操作限制——只能减一不能加模型简单到不需要任何动态规划就是一个贪心加归纳。3. 正确的贪心是倒着扫出来的3.1 先想“最后能变成什么样”贪心题最怕上来就写代码。我现在的习惯是先不问“每一步怎么操作”而是问“最终结果有什么限制”。最终数组设为 b它满足两个条件b 非递减并且因为每个数只能减不能加所以 b[i] a[i]。既然目标是最小化操作次数等价于最大化最终数组的总和 sum(b)。所有 b[i] 都尽可能地大但又必须互相不冲突。这时候看一下第二个条件b[i] a[i]。第三个条件是非递减也就是 b[1] b[2] ... b[n]。把这两个条件放在一起你会发现一个关键点——每个位置的上限不仅被原数组 a[i] 限制还被它右边所有位置的上限限制。因为非递减要求 b[i] b[i1] ... b[n]所以 b[i] 不可能大于它右边任意一个位置的最终值。换句话说右边的数字决定了左边数字的“天花板”。这就是为什么这题要倒着扫你只有先知道右边最终的最小值才能知道当前位置最多保留多少。3.2 为什么不从左往右从左往右的直觉是我保留当前值如果下一个数比当前数小那就把前面拉低。这个过程确实正确但问题在于你需要在发现 a[i] 小于前面某个值时回过头去改前面一大段。如果用一个 naive 循环来做复杂度会变成 O(n^2) 甚至更差要优化就得维护额外数据结构完全是把简单问题复杂化。而且从左往右还有个心理陷阱你总想着“当前前缀保持非递减”于是把注意力放在已经处理过的部分上。可实际上真正能卡住你的是后面还没看过的数。后验信息最关键而正序遍历没法提前知道后面发生了什么。从右往左就不一样。每扫过一个位置我手里就握着“右边所有数字最终的最小值”这个完整信息当前位置只需要和自己的原值比一下就完事整个算法是一遍扫描不需要任何撤销操作。3.3 严格证明它为什么是最优有了直觉再补一个严谨证明以后遇到类似题就能直接用这套逻辑。记最终数组为 b满足b[i] a[i]b[1] b[2] ... b[n]b[i] 都是整数从最后一个位置开始归纳。b[n] 只受 a[n] 限制为了不浪费操作取 b[n] a[n]这是最优的。假设已经构造出 b[i1], ..., b[n]并且知道它们已经是最优的。现在处理 b[i]。因为序列非递减必须满足 b[i] b[i1]又因为 b[i] a[i]所以 b[i] min(a[i], b[i1])。为了让总和最大b[i] 直接取到这个上限也就是b[i] min(a[i], b[i1])如果 a[i] b[i1]说明 a[i] 太大需要降到 b[i1]代价是 a[i] - b[i1]如果 a[i] b[i1]说明 a[i] 自己就是更紧的约束不需要任何操作同时它更新了“右边最小值”这个信息。由于每一步的 b[i] 都取到了可行范围内的最大值且这个选择不会限制后续任何位置的取值它只会让后续位置的约束更宽松或不变所以全局最优。整个贪心就成立。算法的复杂度是 O(n)数组只需要读一遍不需要排序不需要额外数据结构。4. AC 代码与实现细节4.1 C17 参考代码下面是这道题的核心实现支持多组测试用例。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } long long ans 0; long long mn a[n - 1]; // 当前“右边所有数的最终最小值” for (int i n - 2; i 0; i--) { if (a[i] mn) { ans a[i] - mn; // 需要把 a[i] 压到 mn } else { mn a[i]; // a[i] 更小更新限制 } } cout ans \n; } return 0; }代码非常短真正核心的循环只有不到十行。这也是这类“思维量大、代码量小”题目的典型特征一旦你想明白写起来极其顺畅。4.2 纯 C 语言实现要点如果你还在用纯 C 刷题这题的实现反而更简单因为它不需要排序不需要任何 STL 容器。只需要一个 long long 数组和逆序循环。注意 CF 的题通常 n 上限是 2e5所以数组开成 200005 一般够用。#include stdio.h long long a[200005]; int main() { int T; scanf(%d, T); while (T--) { int n; scanf(%d, n); for (int i 0; i n; i) { scanf(%lld, a[i]); } long long ans 0; long long mn a[n - 1]; for (int i n - 2; i 0; i--) { if (a[i] mn) { ans a[i] - mn; } else { mn a[i]; } } printf(%lld\n, ans); } return 0; }C 语言的坑只有一个记得全程用 long long。虽然数组里的每个值看着不大但 n 到 2e5每个位置的代价一累积很容易超过 int 范围。4.3 边界条件和常见 WA 点这道题有几个地方特别容易写错都是我亲眼见过的坑n 1 的时候答案一定是 0因为只有一个数的数组天然满足非递减。上述代码里逆序循环从 n-2 开始会自动跳过不会出错。mn 初始化不能是 0必须初始化为 a[n-1]。如果初始化成 0那么所有正数都会被误判成需要降到 0答案会偏大。数组本身已经非递减的时候答案应该是 0。比如 [1, 2, 3, 4]从右往左扫每个数都不大于当前 mn不会产生任何代价。数组全是同一个值的时候比如 [5, 5, 5]mn 从右往左一直是 5ans 是 0完全正确。最极端的情况是递减数组[5, 4, 3, 2, 1]。这时所有数都需要降到 1代价就是 (5-1) (4-1) (3-1) (2-1) 10。关于长期 WA我个人的经验是如果一道数组操作题的答案需要累加很多次直接无脑用 long long不要去做“会不会超 int”的预判。省那点内存没意义WA 一发的代价远大于它。5. 赛后复盘这类题的识别信号5.1 识别信号的清单打完这场比赛之后我把 C 题的思考过程整理成了一份“遇到此类题怎么快速识别”的清单操作描述里是不是只有“减少”或“增加”一种方向如果是模型大概率不是那种需要来回调整的复杂动态规划。目标是不是“让数组变成有序/非递减/非递增”如果是那么最终状态一定满足一组简单的偏序约束。问的是不是“最少操作次数”如果是那么目标等价于“最大化不操作的保留量”。数据范围是不是 n 在 2e5 左右如果是那正解大概率是 O(n log n) 以下O(n) 贪心是常见答案。这四个信号同时出现时建议你优先考虑“从右往左传限制”的贪心这题基本就跑不掉了。5.2 可复用的两个变体这类题在 CF 里经常以各种变体出现。第一个变体是“只能加不能减”。比如给定数组每次操作把某个数加 1求最少操作让数组严格递增。这时候策略反过来正序扫描就能解决维护上一个位置的值当前数至少要比上一个数大 1不够就补代价累加。核心思维和本题一模一样只不过方向从“后缀最小值限制”变成了“前缀最大值限制”。第二个变体是“严格递增”而不是“非递减”。如果题目要求 a[i] a[i1]可以做一个经典转化令 c[i] a[i] - i然后问题就变成让 c 非递减。这是因为a[i] a[i1] 等价于 a[i] - i a[i1] - (i1)原来的一次减一操作对应着 c[i] 减一所以模型完全不变。很多比赛题都会在这里挖坑如果你不知道这个转化可能会卡在“严格递增”和“非递减”的边界上。5.3 我在 998 C 上的节奏最后说说比赛时的节奏。我当天读 C 题大约花了 5 分钟大部分时间都在琢磨题面的故事到底在讲什么。然后我在草稿纸上把模型写出来又手算了两个例子确认了“从右向左传最小值”的思路再花 5 分钟写代码一次 AC。整个过程最耗时的不是代码而是“敢不敢把题意删到只剩骨架”。这个经验我觉得比题目本身更值钱。Div3 的 C 题绝大多数都不需要冷门算法它考的就是你能不能快速把一个看似复杂的题干压缩成一个简单的数学结构。所谓“会者不难”那些人不是见过这道题只是他们删废话的速度比你快罢了。以后遇到这种“某个数组通过若干次单点操作满足一种顺序约束”的问题不用慌先想最终状态长什么样再看哪一边能提供约束最后从约束最强的那一端扫回来。这套流程跑下来哪怕原题换个故事背景你也能稳稳拿分。