企业官网建设流程全解析

2014年12月的这轮CCS-CSP，第三题叫“集合竞价”。很多人在考场上第一反应是“又一道模拟题”，第二反应是“撮合规则终于看明白了”，第三反应可能就是“价格该怎么处理”。这道题放在第三题的位置，难度很微妙：数据量不大，暴力能过，但想一次写对并不轻松。它同时考察了三样东西：对指令型输入的处理能力、对撮合规则的理解，以及一个很多人容易忽略的细节——金额类数据千万别用浮点数直接比较。

如果你正在准备类似的能力认证，或者想找一道既能练手、又能带出“枚举 + 有序性优化”思路的题目，这道“集合竞价”非常值得完整复盘。下面我从题意拆解、设计思路、代码实现到避坑经验，把整道题完整过一遍。

1. 题目在考什么：需求拆解与撮合规则

1.1 三类指令与输入格式

这道题的输入没有预先告诉你有多少行，而是直接给出一系列记录，读到文件结束为止。每条记录按行号从 1 开始编号，总共分成三种类型：

• buy 价格 股数：表示有人愿意以不低于该价格买入指定股数。
• sell 价格 股数：表示有人愿意以不高于该价格卖出指定股数。
• cancel 行号：表示撤销之前第“行号”条记录，被撤销的记录不再参与任何成交计算。

价格是两位小数的浮点数，股数是整数。没有明显的“结束标记”，所以程序需要用while (scanf(...) == 1)之类的循环一直读到 EOF。这个输入结构本身就是一个考点：很多人习惯先读一个 n 再循环，遇到没有 n 的输入就懵了。

一个典型的输入片段长这样：

buy 9.25 100 sell 9.25 100 cancel 1 buy 8.88 175 sell 9.00 200 buy 9.00 400 sell 8.00 500

这里的cancel 1表示把第 1 行那条buy 9.25 100作废。作废之后，它既不能作为买单参与匹配，它的价格也不应该出现在候选开盘价里。

1.2 开盘价与成交量怎么算

这是整道题的核心。系统要选择一个“开盘价” p，然后按下面的规则撮合：

• 所有买入价格 >= p 的买单都可以成交，因为这些买家愿意以不低于 p 的价格买。
• 所有卖出价格 <= p 的卖单都可以成交，因为这些卖家愿意以不高于 p 的价格卖。
• 最终成交量是 min(总买单股数, 总卖单股数)。

为什么是 min？因为成交必须买卖双方数量匹配。买盘有 1000 股意愿，卖盘只有 300 股意愿，那最多只能成交 300 股；反过来也一样。多余的那部分意愿无法形成交易。

题目最终要求：在所有可能的开盘价中，找到能产生最大成交量的那个价格；如果多个价格产生的最大成交量相同，取其中最高的价格。

用一个生活化的类比来理解：菜市场门口有个收购站，买家和卖家都报了心理价位，工作人员喊一个“开盘价”。报价比喊价高或相等的卖家愿意卖，出价比喊价低或相等的买家愿意买。只要两边数量对得上就成交，对不上的部分只能干瞪眼。喊价高了，卖家愿意卖的多、买家愿意买的少；喊价低了，反过来。所以一定存在一个中间区间，能让成交量达到最大。

1.3 这题为什么值得写

这道题表面上是个模拟，其实已经带了一点“算法设计”的味道。你很容易想到枚举价格，但价格是连续实数，不能真的把所有实数枚举一遍。这里需要意识到：答案只可能落在某些特殊价格上。把这个想通，题目就从“暴力枚举浮点数”变成了“离散化 + 枚举”。

另外，价格精度也是这道题的隐藏陷阱。如果直接用double存价格、直接和double比较大小，在某些边界数据上会出现精度问题，比如 0.29 和0.29在浮点表示里可能并不严格相等，导致本应匹配的记录没有被匹配。这种错误最坑的是：小数据全对，大数据偶尔错一个，而且不对拍根本查不出来。

2. 设计思路：把题面翻译成能跑的逻辑

2.1 价格全部转成整数

我拿到题目第一个决定就是：所有价格一律以“分”为单位存成long long。价格本身最多两位小数，乘以 100 后必然是整数，这就彻底避开了浮点比较带来的不确定性。

读入时先读一个double，再乘 100 转成整数。这里有个细节：不要直接(long long)(p * 100)，因为浮点乘法可能得到924.9999999，强转直接变成 924。稳妥做法是四舍五入：

long long priceInCents = (long long)(p * 100 + 0.5);

或者直接用llround(p * 100)。把价格转成整数之后，后面所有比较、排序、枚举都是整数运算，输出时再除以 100.0 恢复成带两位小数的形式。

提示：凡是题目里出现“金额”“价格”这类带小数的量，先想清楚是不是可以放大成整数处理。这个习惯能帮你避开大量浮点精度问题。

2.2 撤销指令的处理顺序

处理cancel时要特别注意行号序号从 1 开始。我习惯在 vector 里先塞一个占位元素，让下标从 1 开始，这样cancel x直接对应records[x]，不用每次减一。

标准做法是：读入一条cancel x后，把第 x 条记录的valid标记置为 false。这道题的前提通常保证被撤销的记录是 buy 或 sell 指令，所以一次标记就够了。如果你看到某些题解说遇到取消指令还要递归处理“被撤销的指令本身也是 cancel”的情况，那是考虑得更保守，但大多数数据用不到。

还有一个容易忽略的点：撤销指令这一行本身也是一条记录，它也会占据一个行号。后续如果又有cancel y指向它，要保证程序不会越界，同时重复撤销同一行不会出问题。用布尔标记就能天然处理重复撤销。

2.3 为什么只用枚举出现过的价格

开盘价是一个实数，直接枚举肯定不行。问题的关键是证明：最优开盘价一定等于某条有效买单或有效卖单的价格。

理由是这样的：随便取一个开盘价 q，如果 q 没有落在任何记录价格上，那么 q 一定位于两个相邻记录价格之间的某个开区间里。在这个区间内平移 q，所有买单的“价格 >= q”条件不会变，所有卖单的“价格 <= q”条件也不会变，因此成交量完全不变。既然在一个区间内怎么移动都等价，而题目又要求“最大成交量相同时取最高价”，那我们自然应该取这个区间的右端点。右端点一定是一个有效记录价格。

所以候选价格集合就是所有有效 buy/sell 记录的价格去重后的结果。把被撤销记录的价格也加进去会导致候选价格变多，但不会影响答案，只是浪费时间。

2.4 成交量的单调性

搞清楚候选价格之后，可以再往深看一层。设：

• B(p) = 所有买入价 >= p 的买单总股数，这个值随 p 增大单调不增。
• S(p) = 所有卖出价 <= p 的卖单总股数，这个值随 p 增大单调不减。
• V(p) = min(B(p), S(p))。

当 p 很小时，买单非常多、卖单非常少，V(p) 由 S(p) 决定，会随着 p 增大而增大；当 p 很大时，卖单非常多、买单非常少，V(p) 由 B(p) 决定，会随着 p 增大而减小。所以 V(p) 是一个先增后减的“单峰函数”。

这个性质直接告诉我们：题目没有要求输出最大成交量对应的所有价格，而是取最高价，所以按价格升序枚举并维护最大值即可。这个单调性也为后面的双指针优化埋下伏笔。

3. 实操：从读入到输出的完整实现

3.1 数据结构与读入代码

我定义了一个简单的结构体：

struct Record { int type; // 0 表示 buy，1 表示 sell，2 表示 cancel long long price; // 价格，单位：分 long long vol; // 股数 bool valid; // 是否有效 };

读取部分直接按 EOF 处理：

#include <cstdio> #include <vector> #include <algorithm> using namespace std; struct Record { int type; long long price; long long vol; bool valid; }; int main() { vector<Record> rec; rec.push_back({-1, 0, 0, false}); // 占位，下标从 1 开始 char op[16]; while (scanf("%s", op) == 1) { Record r; r.valid = true; r.vol = 0; if (op[0] == 'b') { double p; long long v; scanf("%lf%lld", &p, &v); r.type = 0; r.price = (long long)(p * 100 + 0.5); r.vol = v; } else if (op[0] == 's') { double p; long long v; scanf("%lf%lld", &p, &v); r.type = 1; r.price = (long long)(p * 100 + 0.5); r.vol = v; } else { // cancel long long x; scanf("%lld", &x); r.type = 2; r.price = 0; rec[(int)x].valid = false; } rec.push_back(r); } // 后续处理 return 0; }

注意cancel分支里，rec[(int)x]必须是已经存在的记录，否则说明输入不合法。我习惯在更新记录之前先处理撤销标记，再把当前这条 cancel 记录本身 push 进去，这样顺序不会乱。

3.2 朴素枚举写法

处理完输入后，第一版可以用最直观的双重循环：枚举所有候选价格，对每个价格扫一遍全量记录。

vector<long long> prices; int n = (int)rec.size() - 1; for (int i = 1; i <= n; i++) { if (rec[i].valid && (rec[i].type == 0 || rec[i].type == 1)) { prices.push_back(rec[i].price); } } sort(prices.begin(), prices.end()); prices.erase(unique(prices.begin(), prices.end()), prices.end()); long long ansPrice = 0, ansVol = 0; for (long long p : prices) { long long buySum = 0, sellSum = 0; for (int i = 1; i <= n; i++) { if (!rec[i].valid) continue; if (rec[i].type == 0 && rec[i].price >= p) { buySum += rec[i].vol; } else if (rec[i].type == 1 && rec[i].price <= p) { sellSum += rec[i].vol; } } long long vol = min(buySum, sellSum); if (vol > ansVol || (vol == ansVol && p > ansPrice)) { ansVol = vol; ansPrice = p; } } printf("%.2f %lld\n", ansPrice / 100.0, ansVol);

这段代码最坏情况是 O(n²)。本题 n 通常只有几千，双重循环也就是几千万次运算，实际跑起来非常快。如果你不确定数据范围，可以先写这个版本保底，毕竟它逻辑清晰、不容易写错。

3.3 扫描线双指针优化

如果你想在这个题目上多学一点，可以顺着“单调性”继续想：p 从小到大移动时，B(p) 只会减少，S(p) 只会增加。既然如此，提前把买单按价格升序排序，卖单也按价格升序排序，然后用两个指针维护。

• 初始时买量总和是所有有效买单之和。
• p 每变大一次，就把买单里价格严格小于 p 的量从买量总和中减掉。
• 把卖单里价格小于等于 p 的量加入卖量总和。

这样每个价格的处理变成均摊 O(1)，整体复杂度 O(n log n)。

vector<pair<long long, long long>> buys, sells; for (int i = 1; i <= n; i++) { if (!rec[i].valid) continue; if (rec[i].type == 0) buys.push_back({rec[i].price, rec[i].vol}); else if (rec[i].type == 1) sells.push_back({rec[i].price, rec[i].vol}); } sort(buys.begin(), buys.end()); sort(sells.begin(), sells.end()); long long buySum = 0; for (auto &e : buys) buySum += e.second; long long sellSum = 0; int bi = 0, si = 0; long long ansVol = 0, ansPrice = 0; for (long long p : prices) { while (bi < (int)buys.size() && buys[bi].first < p) { buySum -= buys[bi].second; bi++; } while (si < (int)sells.size() && sells[si].first <= p) { sellSum += sells[si].second; si++; } long long vol = min(buySum, sellSum); if (vol > ansVol || (vol == ansVol && p > ansPrice)) { ansVol = vol; ansPrice = p; } }

这个版本我第一次写的时候也花了一点时间理清两个 while 的边界条件：买单价严格小于 p 的不能成交，卖单价小于等于 p 的可以成交。边界条件一错，答案就差之毫厘。

3.4 输出与格式化细节

输出开盘价保留两位小数，成交量是整数。

printf("%.2f %lld\n", ansPrice / 100.0, ansVol);

这里ansPrice / 100.0会自动变成浮点数，%.2f正好保留两位。有人会写成ansPrice / 100，那就变成整数除法了，价格直接按分输出，肯定不对。

还有一点：如果最终ansVol为 0，说明没有任何价格能让买卖双方成交，按题目常见的判读方式输出0.00 0是合理的。代码里ansPrice和ansVol初始值已经是 0，所以不用额外处理。

4. 边界用例与错误排查实录

4.1 两个自测用例

我一般写完代码不会直接提交，而是先构造几个边界用例自己跑一遍。

第一个用例非常简单，只有一条买单和一条卖单：

buy 9.25 100 sell 8.75 100

价格 9.25 时，买单成交 100，卖单价 8.75 <= 9.25，也成交 100，成交量 100；价格 8.75 时，买单 9.25 >= 8.75，成交 100，卖单也成交 100，成交量还是 100。两个价格成交量相同，按规则取最高价，所以输出9.25 100。这个用例专门验证“多解取最高价”。

第二个用例我设计成包含撤销指令，验证cancel是否正确生效：

buy 9.25 100 sell 9.25 100 cancel 1 buy 8.88 175 sell 9.00 200 buy 9.00 400 sell 8.00 500

第 1 行被撤销后，有效买单只剩 8.88 的 175 股和 9.00 的 400 股；有效卖单是 9.25 的 100 股、9.00 的 200 股和 8.00 的 500 股。

• p = 8.88 时，买单总股数 575，卖单中 8.00 的 500 股可成交，成交量 500。
• p = 9.00 时，买单只剩 400，卖单增加 9.00 的 200 股，可成交 700，但 min(400, 700) = 400。
• p = 9.25 时，买单为 0。

所以答案是8.88 500。这个用例能同时验证撤销、边界价格和撮合规则三件事。

4.2 常见问题速查表

我把写这题时可能踩的坑整理成了一张表：

这些坑里，最阴险的是第一条。浮点问题在小数据上很难暴露，因为整数价格恰好能被 double 精确表示；一旦出现类似 7.29 这样的价格，浮点误差就可能让比较结果偏离预期。我当初就是被 0.29 这个不起眼的数字教育过，从那以后凡是题目里出现金额，一律整型化。

4.3 一个小习惯：写对拍

如果你想验证优化版代码是否正确，最好的办法不是自己瞪眼，而是写一个朴素版，然后随机生成数据对拍。生成器只需要随机产生 buy/sell/cancel 指令，保证 cancel 行号合法即可。跑上几十万组数据，如果两个版本答案完全一致，正确性就有了基本保障。

对拍脚本很简单，一个循环里执行三次：生成数据、运行朴素版、运行优化版，再用 diff 比较输出。这个习惯不仅适用于这道题，几乎所有“有标准暴力做法”的算法题都适用。

5. 从算法到真实撮合场景

5.1 真实市场怎么撮合

“集合竞价”这个词不是出题人凭空造的。在很多证券市场的开盘阶段，系统会收集一段时间内的买卖申报，按某个原则确定一个开盘价，让成交量尽可能大。高于开盘价的买单和低于开盘价的卖单会优先成交，这跟题目的撮合规则本质一致。

不过真实场景更复杂，通常还涉及“价格优先、时间优先”的排序：同一价格下先提交的订单先成交，可能在开盘价上下分多档进行连续撮合。这道题做了大量简化，只要求选出一个统一价格，然后按总量配对。

但核心思想是共通的：用“最大成交量”作为目标函数，去寻找一个最优价格。把这道题的算法吃透，再去理解真实撮合引擎的“逐笔撮合”逻辑，会轻松不少。

5.2 如果再扩大数据范围

如果题目把 n 从几千放大到几十万，O(n²) 的朴素枚举就不行了，需要采用前文写的双指针扫描，甚至可以用离散化加前缀和：

先按价格排序，对应每个价格统计“买入价大于等于该价格的累计买量”和“卖出价小于等于该价格的累计卖量”，然后枚举价格时直接查表。这个过程本质上就是三维版本的前缀和思想。

再进一步，如果有人问你“动态增加订单怎么办”，那就可以往树状数组、线段树的方向想：按价格建立权值线段树，买单和卖单分别维护，插入和删除时更新总量并查询某个价格下的成交量峰值。当然这就超出这道题的范畴了，但作为扩展思路很有意思。

回到题目本身，我个人刷这道题最大的收获不是学会了枚举，而是养成两个习惯：第一，金额类数据一律转整数；第二，写优化代码之前先想清楚函数的单调性。建议你也手写一遍朴素版，再写一遍双指针版，然后自己构造几个边界用例丢进去跑一遍。这个过程比单纯看十篇题解都管用。