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 天然就能同时拿到两端
我是这么安排数据结构的：
map<int, long long> bid：价格作为 key，数量作为 value。因为是 map，key 从小到大排。map<int, 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 完整代码
下面这份代码是基于 C++11 写的，只用了标准库的 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; map<int, 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);如果你用 C++11 之后的标准库，也可以用prev(bid.end())来替代这两行，效果一样。
5.3 数量类型用 int 会爆
这道题输入的 qty 看起来不大，但是在同一个价格上会不断累加，撮合时还要做减法。如果你只开map<int, int>，遇到数据稍微猛一点的测试点，累加过程就可能溢出。尤其是多个价格档位反复出现，同一个 key 被多次插入，数量很容易超过 int 上限。
建议从一开始就写map<int, long long>，qty 也读成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。它的代码量小，调试也直观，打印出来能看到每个价格上的数量。写完之后不要急着删调试输出，拿样例跑一遍，重点关注撮合结束后最优价格是否还停留在已经清零的档位上。
这道题虽然名字带股票，本质上还是“读懂规则 + 选对容器 + 小心迭代器”。你真正掌握的，不只是怎么模拟股票行情，更是怎么把一堆零散事件在一个有序容器里维护得干净利落。以后遇到订单簿、日程表、区间覆盖这类题，会非常有帮助。
