1. 项目概述从一道题看数据结构的实战价值最近在洛谷上刷题又遇到了老朋友 P2234 “营业额统计”。这道题别看它来自2002年的 HNOI湖南省队选拔题目描述也带着点“古早味”但它在算法竞赛圈子里尤其是对于正在学习数据结构的同学来说绝对是一道绕不开的经典。为什么因为它把一个看似是数学统计的问题巧妙地转化为了一个对数据结构基本功的极致考验。题目要求我们计算公司每天营业额的最小波动值之和这个“最小波动值”的定义是当天营业额与之前所有天营业额中差值绝对值最小的那个。换句话说对于第i天的营业额a[i]我们需要在a[1]到a[i-1]这个历史数据集合里找到与a[i]最接近的那个数前驱或后继。你可能会想这不就是遍历一下前面i-1个数找最小差值吗如果n最大是 32767最坏情况下的时间复杂度是 O(n²)那可是超过 10^9 次运算妥妥地超时。所以这道题的核心挑战在于如何高效地在一个动态增长的集合中为每一个新加入的元素快速找到与其最接近的值。这正是平衡二叉搜索树BST的拿手好戏。今天我就结合自己多次实现和调试这道题的经验用 C 带你从零开始不仅把这道题 AC 了更要弄明白背后的数据结构选型、实现细节以及那些容易踩坑的地方。无论你是刚学完 STLset想练练手还是打算手搓一个平衡树来加深理解这篇文章都会给你带来实实在在的收获。2. 核心思路与数据结构选型分析2.1 问题本质与暴力解法的局限性我们先彻底吃透题意。设第i天的营业额为val我们需要计算min(|val - a[j]|)其中j从 1 到i-1。这个“最小绝对差值”等价于在历史数据集合S中寻找val的前驱小于等于val的最大值和后继大于等于val的最小值。然后最小波动值就是min(val - 前驱, 后继 - val)。第一天没有历史数据按照定义其最小波动值就是它自身的营业额。最直接的暴力方法就是模拟这个过程用一个数组记录所有历史营业额。对于第i天遍历数组的前i-1个元素更新最小差值。代码简单但复杂度为 O(n²)。代入n32767计算量级约为 5.3 亿次比较和绝对值运算在典型的竞赛时间限制1秒内是绝对无法通过的。这就迫使我们寻找更优的数据结构。2.2 平衡二叉搜索树为何是唯一正解我们需要一个数据结构支持以下两种核心操作插入Insert将第i天的营业额加入集合。查询前驱/后继Predecessor/Successor在当前的集合中快速找到与给定值最接近的两个数。二叉搜索树BST天生就是为了这种“动态有序集合”的查找而生的。在理想情况下树是平衡的插入和查找的时间复杂度都是 O(log n)。对于本题n32767log2(32767) ≈ 15总时间复杂度约为 O(n log n)完全在可接受范围内。但是普通的 BST 有一个致命弱点如果输入数据是有序的比如营业额单调递增或递减BST 会退化成一条链深度变为n时间复杂度退化回 O(n²)和暴力法没有区别。题目虽然没有明确说明数据是否有序但我们必须考虑最坏情况。因此我们需要能保持平衡的二叉搜索树即平衡二叉搜索树。注意很多同学第一次做这道题知道要用“树”但忽略了“平衡”二字自己实现了一个普通 BST结果提交后有几个测试点超时就是因为数据可能存在有序或近似有序的情况。2.3 C实现方案对比STL set 与手写平衡树对于竞赛和实践我们主要有两种实现路径方案一使用 C STL 中的setstd::set是基于红黑树一种自平衡二叉搜索树实现的它自动维护树的平衡提供了insert,lower_bound,upper_bound等成员函数可以非常方便地找到前驱和后继。优点代码极其简洁不易出错开发效率高。缺点set的迭代器操作需要小心特别是处理边界情况并且由于其封装性对树内部结构的理解帮助有限。lower_bound返回的是大于等于给定值的迭代器要找到严格小于给定值的前驱需要稍微绕一下。方案二手写平衡树如 Treap, Splay, AVL手动实现一个平衡树数据结构。优点对数据结构的理解提升巨大可以完全掌控所有操作并且能处理更复杂的问题比如区间操作、名次树等set无法直接完成。缺点代码量大调试复杂容易写错。对于本题我强烈推荐初学者和希望快速 AC 的同学使用std::set。它的性能完全足够且代码量可能只有手写树的十分之一。本文也将以set的实现作为主线进行详解并在最后部分探讨手写 Treap 的思路供学有余力的同学参考。3. 基于 STL set 的详细实现与代码解析3.1 算法流程设计使用set解决本题的步骤非常清晰初始化一个空的setint用于存储历史营业额初始化总和ans 0。读入总天数n。读入第一天的营业额first_val。根据题意第一天的最小波动值就是其本身所以ans first_val并将first_val插入set。对于第2天到第n天 a. 读入当前营业额val。 b. 在set中寻找val的后继使用set.lower_bound(val)它返回指向第一个不小于val的元素的迭代器。 c. 在set中寻找val的前驱后继的迭代器it的前一个位置--it可能就是前驱。但需要仔细处理边界条件。 d. 计算当前最小波动值delta分别计算val与找到的前驱、后继的差值绝对值如果存在取最小值。 e. 将delta累加到ans。 f. 将val插入set供后续天数查询。输出ans。3.2 关键操作如何准确找到前驱和后继这是实现的核心也是容易出错的地方。我们需要考虑几种边界情况集合为空这只发生在第一天我们已经特殊处理。val在集合中已存在此时最小波动值为 0。lower_bound(val)会返回指向这个val的迭代器它既是“后继”大于等于我们也可以用它找到前驱需要判断。val比集合中所有数都小此时lower_bound(val)返回set.begin()即最小的元素它是val的后继。val没有严格意义上的前驱因为前驱应该小于val。val比集合中所有数都大此时lower_bound(val)返回set.end()这是一个尾后迭代器不能解引用。val的前驱是集合中的最大元素。具体代码逻辑如下#include iostream #include set #include climits // 用于 INT_MAX #include cmath // 用于 abs using namespace std; int main() { int n; cin n; setint company; int first_val; cin first_val; long long ans first_val; // 注意用 long long 防止溢出 company.insert(first_val); for (int i 2; i n; i) { int val; cin val; // 寻找后继第一个 val 的数 auto it_succ company.lower_bound(val); // 初始化最小差值为一个很大的数 int delta INT_MAX; // 情况1找到了后继 (it_succ ! company.end()) if (it_succ ! company.end()) { delta min(delta, abs(*it_succ - val)); } // 情况2寻找前驱。前驱是第一个 val 的数即 it_succ 的前一个位置 // 如果 it_succ 指向 begin()则没有前驱 if (it_succ ! company.begin()) { auto it_pred prev(it_succ); // 等同于 --it_succ但更安全 delta min(delta, abs(*it_pred - val)); } // 注意如果 val 本身在集合中那么 it_succ 指向 val // it_pred 指向比 val 小的最大数delta 通过 min 比较会得到 0。 ans delta; company.insert(val); } cout ans endl; return 0; }3.3 代码逐行解读与易错点分析数据类型与溢出结果保证小于2^31但我们在累加过程中使用int可能在中途溢出。因此ans应使用long long。这是竞赛中非常常见的陷阱。lower_bound的使用set.lower_bound(val)是成员函数时间复杂度为 O(log n)。不要误用全局的std::lower_bound(set.begin(), set.end(), val)那样是线性复杂度 O(n)。迭代器边界检查解引用set.end()或--set.begin()是未定义行为会导致运行时错误。因此在使用*it前必须判断it ! company.end()在执行--it或prev(it)前必须判断it ! company.begin()。prev函数prev(it_succ)是 C11 中的标准库函数返回it_succ前一个位置的迭代器。它比直接写--it_succ更清晰且it_succ本身不会被改变。如果改变了it_succ可能会影响后续对后继的判断。重复元素处理set本身不允许重复元素。如果某天营业额和之前某天完全相同company.insert(val)不会插入新元素但返回的 pair 中 second 为 false。不过这对我们的算法没有影响因为我们在插入前已经计算完了当天的波动值。即使集合中已存在vallower_bound会指向它delta计算结果为 0完全正确。实操心得在写这类涉及迭代器操作的代码时我习惯先用笔画一下几种边界情况最大、最小、相等然后对照代码看每个分支是否被正确处理。这种“脑内调试”能避免很多低级错误。4. 性能分析与扩展面对更大数据的思考我们的set解法时间复杂度为 O(n log n)空间复杂度 O(n)。对于本题的 n≤32767 游刃有余。即使在常见的 1秒 时限下也完全足够。但我们可以思考一下如果数据量扩大到n ≤ 10^6甚至更大O(n log n)依然高效吗理论上log2(10^6) ≈ 20运算量级在千万次配合现代 CPU 通常可以在 1 秒内完成。但常数因子很重要。std::set由于红黑树的复杂旋转操作和节点内存非连续其常数比数组结构大。在极端追求性能的场景例如n10^7我们可能会考虑其他数据结构手写 Treap (树堆)基于随机化的平衡 BST代码比红黑树简单平均效率很高且常数较小。手写 Splay (伸展树)同样可以实现并且有“局部性”的特点访问过的节点会被提到根部对于某些访问模式有奇效。离线处理 排序 二分如果所有数据已知离线我们可以先全部读入然后进行排序。对于第i天的数据在排序后的前i-1个数据中二分查找前驱后继。但这需要维护一个有序列表并支持快速插入用数组实现插入是 O(n) 的反而更慢。可以使用块状链表或树状数组离散化来优化但思维复杂度陡增。对于本题和绝大多数竞赛场景std::set是最佳选择在简洁性、可靠性和性能之间取得了完美平衡。5. 从 set 到手写 Treap深入数据结构内部为了更深刻地理解平衡树是如何工作的我们尝试手写一个 Treap 来解决本题。Treap 是 Tree 和 Heap 的结合每个节点除了键值key营业额还有一个随机生成的优先级priority。它同时满足二叉搜索树左子树所有键值 根节点键值 右子树所有键值和堆根节点优先级高于子节点优先级的性质。通过随机化的优先级Treap 能以很高的概率保持平衡。5.1 Treap 节点设计与核心操作我们首先定义节点结构体并实现左右旋操作来维护堆性质。#include iostream #include cstdlib #include climits #include cmath using namespace std; struct Node { int key; // 营业额 int priority; // 随机优先级 Node *left, *right; Node(int val) : key(val), priority(rand()), left(nullptr), right(nullptr) {} }; // 右旋 (以y为根) void rightRotate(Node* y) { Node* x y-left; y-left x-right; x-right y; y x; // 更新根节点 } // 左旋 (以x为根) void leftRotate(Node* x) { Node* y x-right; x-right y-left; y-left x; x y; // 更新根节点 }5.2 Treap 的插入与查找前驱后继插入操作是 Treap 的核心。它先像普通 BST 一样递归插入到叶子节点然后通过旋转左旋/右旋将新节点“上浮”直到其优先级满足堆的性质。// 插入键值 key void insert(Node* root, int key) { if (root nullptr) { root new Node(key); return; } if (key root-key) { insert(root-left, key); // 如果左子节点的优先级更大需要右旋 if (root-left-priority root-priority) { rightRotate(root); } } else { // 允许重复键值本题可以但通常Treap不允许。我们这里假设无重复或重复时波动为0插入与否不影响。 insert(root-right, key); // 如果右子节点的优先级更大需要左旋 if (root-right-priority root-priority) { leftRotate(root); } } }查找前驱和后继的逻辑与 BST 一致前驱从根开始如果当前节点键值 key则向左子树找否则用当前节点更新答案并向右子树找。后继从根开始如果当前节点键值 key则向右子树找否则用当前节点更新答案并向左子树找。// 查找小于 key 的最大值前驱 int findPredecessor(Node* root, int key) { int pred INT_MIN; // 用一个很小的数初始化 while (root ! nullptr) { if (root-key key) { pred root-key; // 当前节点是候选 root root-right; // 尝试找更大的但依然小于key } else { root root-left; // 当前节点太大向左找更小的 } } return pred; } // 查找大于 key 的最小值后继 int findSuccessor(Node* root, int key) { int succ INT_MAX; // 用一个很大的数初始化 while (root ! nullptr) { if (root-key key) { succ root-key; // 当前节点是候选 root root-left; // 尝试找更小的但依然大于key } else { root root-right; // 当前节点太小向右找更大的 } } return succ; }5.3 基于 Treap 的完整解题代码将上述部分组合起来并注意内存管理本题可以省略程序结束即释放。#include iostream #include cstdlib #include climits #include cmath using namespace std; struct Node { /* 同上 */ }; void rightRotate(Node* y) { /* 同上 */ } void leftRotate(Node* x) { /* 同上 */ } void insert(Node* root, int key) { /* 同上 */ } int findPredecessor(Node* root, int key) { /* 同上 */ } int findSuccessor(Node* root, int key) { /* 同上 */ } int main() { srand(time(0)); // 初始化随机种子 int n; cin n; Node* root nullptr; int first_val; cin first_val; long long ans first_val; insert(root, first_val); for (int i 2; i n; i) { int val; cin val; int pred findPredecessor(root, val); int succ findSuccessor(root, val); int delta INT_MAX; if (pred ! INT_MIN) { // 前驱存在 delta min(delta, abs(val - pred)); } if (succ ! INT_MAX) { // 后继存在 delta min(delta, abs(succ - val)); } // 如果 val 已在树中pred 和 succ 至少有一个等于 valdelta 会被更新为 0。 ans delta; insert(root, val); } cout ans endl; // 实际应用中应添加销毁树的代码释放内存 return 0; }注意事项手写 Treap 需要注意几个关键点。一是随机数种子srand最好用time(0)但注意在多次调用时不要重复初始化。二是递归插入的旋转操作一定要更新引用(Node* root)确保旋转后父节点能指向新的子根。三是查找前驱后继的 while 循环条件以及用INT_MIN/INT_MAX来标识不存在的情况。调试手写树时建议先写一个中序遍历函数打印树结构验证插入是否正确。6. 常见问题与调试技巧实录即使思路清晰实现这道题时还是会遇到一些典型的“坑”。下面是我和许多同学在实战中遇到过的问题及解决方法。Q1: 使用set的代码样例过了但提交后 WA (Wrong Answer)。检查点1第一天的处理。题目明确说“第一天的最小波动值为第一天的营业额”。你的代码是否直接将第一个数加到了总和里是否在计算第二天波动值前才插入第一个数顺序错误会导致第一天被错误地当作历史数据查询。检查点2ans的数据类型。虽然结果保证小于2^31但中间累加过程可能溢出int范围。务必使用long long。检查点3前驱后继的边界条件。当val是集合中最小或最大时你的delta计算是否正确例如如果只有后继没有前驱delta应该等于后继 - val而不是某个初始值。我的代码中通过INT_MAX初始化和条件判断来处理。检查点4输入输出。确保使用cin/cout或scanf/printf一致。在大量数据输入时可以加入ios::sync_with_stdio(false); cin.tie(0);来加速cin/cout。Q2: 手写 Treap 编译通过但运行结果不对或程序崩溃。检查点1指针未初始化。新建节点时left和right指针是否初始化为nullptr检查点2旋转操作写错。这是最易错的地方。画图对照着图检查左右旋代码中指针的重新指向顺序。确保旋转后树的二叉搜索树性质不变。检查点3递归插入的引用传递。insert(Node* root, ...)中的至关重要它确保了对根节点指针的修改能传递回上一层。如果漏了旋转就白做了。检查点4查找前驱后继的逻辑。用一组简单数据如[5, 1, 2]手动模拟看你的findPredecessor和findSuccessor函数返回的值是否正确。Q3: 程序超时 (TLE)。对于set解法几乎不可能超时。如果超时检查是否错误地使用了全局std::lower_bound而不是成员函数set::lower_bound。对于手写树解法大概率是树的平衡性出了问题退化成链。检查插入逻辑和旋转条件是否正确。确保优先级是随机的srand已调用。可以尝试输出树的高度来验证。调试技巧小数据对拍写一个暴力求解的程序O(n²)用随机生成的小数据n10运行两个程序对比结果。这是查找逻辑错误最有效的方法。打印中间状态在set版本中可以在每次插入后打印set的内容用迭代器遍历。在手写树版本中实现一个中序遍历函数inorderPrint打印每个节点的 key 和 priority观察树的结构是否平衡。使用调试器在关键函数如旋转、插入处设置断点单步执行观察变量值的变化是否符合预期。这道“营业额统计”题就像一位严格的教练它用看似简单的需求逼着我们去理解并应用“动态有序集合查询”这一核心思想。无论是选择 STLset的“巧劲”还是挑战手写平衡树的“硬功”这个过程本身对编程能力的提升都是实实在在的。最后关于代码风格我个人的习惯是在竞赛中追求速度就用set在平时练习想夯实基础就手写 Treap。把这两种实现都掌握以后再遇到类似问题你就能真正做到心里有底手上有招了。