UVa 12266 Stock Prices 这道题光看标题容易吓人股票价格是不是要先搞一堆金融模型其实它是一道非常经典的数据结构模拟题核心就是维护一个“订单簿”。题目给你一串买报价和卖报价每来一条新订单你要立刻判断买卖双方价格是否交叉、交叉就按规则成交然后输出此刻的最优买价、最优卖价和最近一次成交价。这道题适合拿来练 STL map也适合用来体验什么叫“规则清楚但细节烦人”。很多新手会卡在成交价到底取买价还是卖价这个点上这篇文章就把这个坑说清楚并按 UVa 12266 的原始输入格式给出一份可以直接 AC 的 C 实现。1. 从订单簿到题目规则1.1 订单簿在模拟什么现实里的交易所并不是简单地记录“今天涨了多少”而是维护一个按价格排序的买卖队列。买盘这边叫 bid价格从高到低排列卖盘这边叫 ask价格从低到高排列。所谓“最优买价”就是买盘里最高的那个价格也就是买一“最优卖价”就是卖盘里最低的那个价格也就是卖一。举个例子如果买一价格是 10卖一价格是 9两者交叉了。买方愿意用 10 块钱买卖方愿意 9 块钱卖这单生意理论上就能成。交易所会自动撮合成交量取决于两边挂单的数量。撮合结束后买一和卖一会发生变化同时会记录一个“最近成交价”。UVa 12266 的模型就是这么来的它不要求你处理税费、手续费、涨跌停只要求你管理一张订单簿模拟撮合过程并在每次订单插入后报告当前行情。1.2 UVa 12266 的输入模型这道题的输入不复杂但和很多 OJ 题不太一样的是每个操作处理完以后要立刻输出不是最后统一输出。每组测试数据的第一行是一个整数 n表示接下来有 n 个操作每个操作占一行。操作只有两种B price qty插入一条买单以 price 价格买入 qty 股。S price qty插入一条卖单以 price 价格卖出 qty 股。每次插入完这条订单后如果当前买盘最高的价格已经不低于卖盘最低的价格系统会自动撮合一直撮合到两边价格不再交叉为止。然后立刻输出三个数当前最优买价、当前最优卖价、最近一次成交价。题目没有单独的查询指令每一行操作都相当于一次“行情快照”。这也是很多人在读题时容易迷糊的地方不要等到最后才输出而是边操作边输出。1.3 三个输出值分别是什么输出格式是固定的一行三个值空格隔开。如果没有买盘第一个值输出-如果没有卖盘第二个值输出-如果还没有发生过成交第三个值输出-。这个规则一定要记牢空盘和未成交的情况都会被卡到。输出位置含义空的时候第 1 个当前最高买单价格-第 2 个当前最低卖单价格-第 3 个最近一次成交价格-顺序是买价、卖价、成交价不是卖价、买价。别小看这个顺序写错一次就白交一发。2. 为什么我觉得 map 是最顺手的方案2.1 优先队列为什么让我头疼很多人看到“动态取最大值/最小值”会立刻想到 priority_queue。买盘用一个最大堆卖盘用一个最小堆逻辑上好像是通的。但真正写起来会发现堆的麻烦在于“过期数据”。一个价格对应的数量可能被部分成交也可能被完全成交。完全成交后这个价格应该从堆里删掉。问题是堆只能访问堆顶不能随意删除一个中间元素。你需要打标记做懒删除等这个价格重新出现在堆顶时再检查它是真是假。听起来可以但没有必要。更麻烦的是撮合过程中最优价格本身会发生变化。比如一个买单进来连续吃掉了卖一、卖二、卖三卖盘的最小值不断变化。如果你只用一个最小堆每次吃掉一部分卖单后还要重新 push 剩余数量代码会变得很啰嗦。map 可以直接用迭代器指向当前最优价能查、能改、能删比堆顺手很多。2.2 map 天然就能同时拿到两端我是这么安排数据结构的mapint, long long bid价格作为 key数量作为 value。因为是 mapkey 从小到大排。mapint, long long ask同样用价格做 key数量做 value。买盘要选最高价答案就是bid.rbegin()-first。卖盘要选最低价答案就是ask.begin()-first。这两个端点就是题目要求的“最优买价”和“最优卖价”查起来是 O(1) 遍历到端点整体操作是 O(log m)m 是当前不同价格档位的数量。有人可能会问为什么一个价格不对应一个订单因为题目只关心价格上的总数量不关心谁下的单、什么时间下的单。同一价格的多个订单合并在一起不会影响最优价格也不会影响成交数量所以 map 的聚合写法正好派上用场。2.3 同一价格其实可以合并数量举个例子买盘里已经有 3 笔价格都是 10 的买单数量分别是 2、3、5那我只需要记住买价 10 对应的总量是 10。后面再来一笔价格 10 的买单就在原有数量上继续累加。这样做的好处是插入和删除都变成了一次 map 操作不需要额外维护订单编号。代价自然也有如果题目要求按时间优先处理同一价格的订单就不能这么简单合并。但 UVa 12266 只要输出价格和最近成交价不要求输出“哪个订单成交了”所以合并数量是安全的。同一价格内部怎么分配数量对最终答案没有影响。3. 真正容易写错的撮合规则3.1 买单插入时成交价取卖价处理B price qty时盘面上的卖单是“被动等待”的一方新进来的买单是“主动”的一方。主动买单去扫卖盘应该从最低卖价开始吃吃到的价格就是卖单原先挂出来的价格。举个例子卖一比卖二价格低那买单先和卖一成交成交价就是卖一价格卖一被吃光后再和卖二成交成交价就是卖二价格。模拟代码里每次成交最近成交价都应该更新为当前ask.begin()-first。这部分的 while 循环大概是while (!ask.empty() price ask.begin()-first bid[price] 0) { long long match min(bid[price], ask.begin()-second); lastPrice ask.begin()-first; bid[price] - match; ask.begin()-second - match; if (ask.begin()-second 0) { ask.erase(ask.begin()); } }注意最后要检查bid[price]是不是变成了 0如果是要把这个价格从买盘 map 里删掉否则下一次bid.rbegin()可能指向一个数量为 0 的假档位。3.2 卖单插入时成交价取买价处理S price qty时新进来的卖单是主动方它要去吃买盘。这时的成交价不是卖单自己的价格而是买盘里被吃掉的那个价格也就是bid.rbegin()-first。这是这道题最容易被判错的地方。如果盘面上挂着一笔买单 50数量 10这时候来了一笔卖单 40数量 5。买方愿意最高出 50卖方愿意最低卖 40双方肯定能成交。但成交价到底算 40 还是 50按 UVa 12266 的规则主动卖单去打买盘应该按买盘价格成交所以最近成交价是 50。这也更符合真实行情里的“价格改善”概念卖单没有理由把价格压到 40 才卖出既然买一已经挂到 50那就能卖到 50。对应的撮合循环while (!bid.empty() price bid.rbegin()-first ask[price] 0) { long long match min(ask[price], bid.rbegin()-second); lastPrice bid.rbegin()-first; ask[price] - match; bid.rbegin()-second - match; if (bid.rbegin()-second 0) { auto it bid.end(); --it; bid.erase(it); } }这里有一个小细节bid.rbegin()是反向迭代器不能直接拿来当普通迭代器 erase。要删除买盘最贵的那一档正确的做法是先拿到bid.end()减一得到最后一个正向迭代器再 erase。这个细节不处理好编译倒是不会报错但运行的时候可能越界。3.3 撮合循环的写法与收敛性买入和卖出的撮合条件刚好是对称的买单触发price ask.begin()-first卖单触发price bid.rbegin()-first核心逻辑就是“主动方价格够不够到被动方的最优价格”。很多人会写反尤其是卖单分支容易写成price ask.begin()-first那就成了卖单去和最低卖价比了完全没意义。这个 while 循环一定会收敛不会死循环。因为每一轮都会让至少一个 map 里的数量变成 0然后被 erase。整个处理过程每个价格档位最多被删掉一次数量只会减少。每一次成交都会执行 min 操作把双方数量里的较小者消耗掉所以循环次数和订单数量、成交批次是同一个量级。4. 可直接参考的 AC 代码4.1 完整代码下面这份代码是基于 C11 写的只用了标准库的 map 和 algorithm提交到 UVa 12266 可以直接用。代码里保留了比较详细的注释方便对照上面讲的撮合规则。#include iostream #include map #include algorithm using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; mapint, long long bid, ask; int lastPrice -1; while (n--) { char op; int price; long long qty; cin op price qty; if (op B) { bid[price] qty; // 主动买单从最低卖价开始吃 while (!ask.empty() price ask.begin()-first bid[price] 0) { long long match min(bid[price], ask.begin()-second); // 买单触发时成交价取卖单价格 lastPrice ask.begin()-first; bid[price] - match; ask.begin()-second - match; if (ask.begin()-second 0) { ask.erase(ask.begin()); } } if (bid[price] 0) { bid.erase(price); } } else { ask[price] qty; // 主动卖单从最高买价开始吃 while (!bid.empty() price bid.rbegin()-first ask[price] 0) { long long match min(ask[price], bid.rbegin()-second); // 卖单触发时成交价取买单价格 lastPrice bid.rbegin()-first; ask[price] - match; bid.rbegin()-second - match; if (bid.rbegin()-second 0) { auto it bid.end(); --it; bid.erase(it); } } if (ask[price] 0) { ask.erase(price); } } if (bid.empty()) cout - ; else cout bid.rbegin()-first ; if (ask.empty()) cout - ; else cout ask.begin()-first ; if (lastPrice -1) cout -; else cout lastPrice; cout \n; } } return 0; }4.2 主循环与输出主循环里每读到一个操作都是先插入对应订单然后立刻撮合最后输出。这里特别说明一下lastPrice的初始值设为-1是把它当成“还没有过成交”的哨兵。股票价格不会是负数所以用-1来判空是安全的。如果你担心测试数据里真的出现价格-1那不可能这道题的所有价格都是正整数。当然更严谨的做法是定义一个单独的布尔变量hasTrade但用-1在实际 AC 代码里非常常见。输出的时候bid.rbegin()-first就是买一ask.begin()-first就是卖一。注意map 为空的时候不能调用 begin 或 rbegin必须先判断 empty再输出-。4.3 复杂度怎么样每次插入操作是 O(log m)m 是当前订单簿里的价格档位数量。撮合过程中每个价格档位最多被删除一次所以整道题的总复杂度是 O(n log n)n 是订单总数。这个复杂度对 UVa 的数据规模来说非常轻松不需要加任何优化。真正影响代码复杂度的不是复杂度本身而是 map 迭代器的处理。只要删除数量归零的档位时小心一点整份代码不会超过 100 行。5. 这些坑我都踩过5.1 撮合条件方向写反我第一次写的时候卖单分支写成了这样while (price ask.begin()-first)看起来好像是在说“卖价够不够低”实际上完全错误。卖单主动触发时应该去和买盘最高价比较也就是price bid.rbegin()-first。方向一错样例都过不了。判断方向的时候脑子里要有画面买单是往上打卖单是往下打。买方看的是自己的价格够不够得着最低卖价卖方看的是自己的价格够不够得着最高买价。5.2 删 map 元素时迭代器失效标准库 map 在 erase 掉一个元素之后指向那个元素的迭代器就失效了。上面代码里我直接写ask.erase(ask.begin());这是安全的因为 erase 的参数是ask.begin()删除之后下一轮循环会重新取 begin。但是在卖单分支删除bid.rbegin()对应元素时不能直接写bid.erase(bid.rbegin());反向迭代器不能直接传给 erase必须转换成正向迭代器。正确写法是auto it bid.end(); --it; bid.erase(it);如果你用 C11 之后的标准库也可以用prev(bid.end())来替代这两行效果一样。5.3 数量类型用 int 会爆这道题输入的 qty 看起来不大但是在同一个价格上会不断累加撮合时还要做减法。如果你只开mapint, int遇到数据稍微猛一点的测试点累加过程就可能溢出。尤其是多个价格档位反复出现同一个 key 被多次插入数量很容易超过 int 上限。建议从一开始就写mapint, long longqty 也读成long long。宁可在类型上多花一点心思也不要 WA 之后去猜是不是数据有坑。5.4 空订单簿的-处理太随意有人会写出这种输出逻辑if (bid.empty()) cout - ; else cout bid.rbegin()-first ;三个输出都这么写没问题是吧但有一个隐藏陷阱最后一个输出后面不要画蛇添足多打一个空格。UVa 对行末空格的容忍度有时很高有时很低按最稳的方式写成-\n比较好。上面的代码在最后用cout \n就是避免这种多余空格问题。还有一点三个值里任何一个为空都只影响它自己不影响其他值。比如买盘为空但卖盘不为空输出应该是- 9 -而不是整体空掉。5.5 只 insert 不清理归零档位如果你把所有价格都留在 map 里哪怕数量已经变成 0也会导致最优价格判断出错。比如买盘最高价已经被吃光了但你还留着这个价格bid.rbegin()-first会告诉你这个已经空掉的档位还能买这显然是错的。所以每轮撮合结束后必须检查主动方那一侧的价格数量是不是变成 0是就 erase。被动方那一侧因为循环里一直在删除不需要额外检查。很多隐性 WA 都是这个原因。6. 一点实战心得6.1 先在纸上把规则理清楚这道题给我的最大感受是动手写代码之前一定要先把撮合规则在纸上走通。不要急着开 IDE。我自己写过一次成交价统一取卖价结果样例直接挂了。后来认真读题才发现主动买单和主动卖单的成交价是相反的。如果你也卡在这个点上可以用一个最简单的例子验证先挂一笔 B 50 10再挂一笔 S 40 5。如果这道题要求最近成交价是 50你就要用“主动卖单吃买盘”的规则如果要求是 40那可能是另一种简化的模拟模型。UVa 12266 属于前者。6.2 用 map 做模拟时的小习惯我现在遇到需要有序映射的模拟题第一反应就是 map。它的代码量小调试也直观打印出来能看到每个价格上的数量。写完之后不要急着删调试输出拿样例跑一遍重点关注撮合结束后最优价格是否还停留在已经清零的档位上。这道题虽然名字带股票本质上还是“读懂规则 选对容器 小心迭代器”。你真正掌握的不只是怎么模拟股票行情更是怎么把一堆零散事件在一个有序容器里维护得干净利落。以后遇到订单簿、日程表、区间覆盖这类题会非常有帮助。