集合竞价

形式化题目

输入买单、卖单和撤单记录。若开盘价为 $p_0$ ，成交量为所有买价 $\geqslant p_0$ 的买单总量与所有卖价 $\leqslant p_0$ 的卖单总量中的较小值。求使成交量最大的开盘价；若成交量相同，选择更高的价格。

思路

先看枚举每个有效报价、重新统计买卖量的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:58
 */
// brute.cpp：小数据暴力解，枚举每个有效报价并重新统计买卖量。
#include <bits/stdc++.h>
using namespace std;

// 一条订单记录：type 为 buy/sell，price 为整数分表示的价格，amount 为股数
struct Order {
    string type;
    int price;
    long long amount;
    bool active; // 是否仍有效（被撤销则置 false）
};

// 把 "xx.xx" 形式的报价转换成整数分，避免浮点误差。
int parse_price(const string &text) {
    int value = 0;
    for (int i = 0; i < (int)text.size(); i++) {
        if (text[i] != '.') {
            value = value * 10 + text[i] - '0';
        }
    }
    return value;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<Order> orders(1);      // orders[1..line] 按输入行号保存订单
    vector<int> candidates;       // 所有出现过买卖报价的行号，作为候选开盘价
    string operation;
    int line = 0;
    while (cin >> operation) {
        line++;
        if (operation == "cancel") {
            int index;
            cin >> index;
            orders[index].active = false;
            continue;
        }

        string price_text;
        long long amount;
        cin >> price_text >> amount;
        if ((int)orders.size() <= line) {
            orders.resize(line + 1);
        }

        Order order;
        order.type = operation;
        order.price = parse_price(price_text);
        order.amount = amount;
        order.active = true;
        orders[line] = order;
        candidates.push_back(line);
    }

    long long best_volume = -1;
    int best_price = 0;
    // 对每个有效报价作为开盘价，重新扫描全部订单统计成交量。
    for (int i = 0; i < (int)candidates.size(); i++) {
        Order &candidate = orders[candidates[i]];
        if (!candidate.active) {
            continue;
        }

        long long buy_volume = 0;
        long long sell_volume = 0;
        for (int j = 1; j < (int)orders.size(); j++) {
            if (!orders[j].active) {
                continue;
            }
            if (orders[j].type == "buy" && orders[j].price >= candidate.price) {
                buy_volume += orders[j].amount;
            }
            if (orders[j].type == "sell" && orders[j].price <= candidate.price) {
                sell_volume += orders[j].amount;
            }
        }

        long long volume = min(buy_volume, sell_volume);
        if (volume > best_volume || (volume == best_volume && candidate.price > best_price)) {
            best_volume = volume;
            best_price = candidate.price;
        }
    }
    if (best_volume < 0) {
        best_volume = 0;
    }
    cout << best_price / 100 << '.' << setw(2) << setfill('0') << best_price % 100;
    cout << ' ' << best_volume << '\n';
    return 0;
}

价格只精确到小数点后两位，因此先把价格转换成整数分，避免浮点误差。撤单后只保留有效订单。

前缀量扫描

对一个候选价 p，成交买量是所有买价不低于 p 的数量，成交卖量是所有卖价不高于 p 的数量。按价格从低到高扫描：买量维护未处理价格的总量，卖量维护已经处理价格的前缀量。每到一个有效报价就计算 min(buy_volume,sell_volume)；使用 >= 更新可以在成交量相同时保留更高价格。

以样例 buy 9.25 100、buy 8.88 175、sell 9.00 1000、buy 9.00 400、sell 8.92 400、cancel 1、buy 100.00 50 为例，撤销第 1 行后有效订单为 8.88、9.00、9.00、8.92、100.00 五笔。按价格升序扫描：

价格	买量（剩余）	卖量（前缀）	成交量
8.88	625	0	0
8.92	450	400	400
9.00	450	1400	450
100.00	50	1400	50

价格 9.00 时买量 = 400 + 50 = 450，卖量 = 1000 + 400 = 1400，成交量 450 最大，因此开盘价为 9.00、成交量为 450。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:58
 */
#include <bits/stdc++.h>
using namespace std;

struct Order {
    string type;
    int price;
    long long amount;
    bool active;
};

int parse_price(const string &text) {
    int value = 0;
    for (int i = 0; i < (int)text.size(); i++) {
        if (text[i] != '.') {
            value = value * 10 + text[i] - '0';
        }
    }
    return value;
}

void erase_order(const Order &order, map<int, pair<long long, long long> > &book,
                 long long &total_buy, long long &total_sell) {
    if (order.type == "buy") {
        book[order.price].first -= order.amount;
        total_buy -= order.amount;
    } else {
        book[order.price].second -= order.amount;
        total_sell -= order.amount;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<Order> orders(1);
    map<int, pair<long long, long long> > book;
    long long total_buy = 0;
    long long total_sell = 0;
    string operation;
    int line = 0;
    while (cin >> operation) {
        line++;
        if (operation == "cancel") {
            int index;
            cin >> index;
            if (orders[index].active) {
                erase_order(orders[index], book, total_buy, total_sell);
                orders[index].active = false;
            }
            continue;
        }

        string price_text;
        long long amount;
        cin >> price_text >> amount;
        Order order;
        order.type = operation;
        order.price = parse_price(price_text);
        order.amount = amount;
        order.active = true;
        if ((int)orders.size() <= line) {
            orders.resize(line + 1);
        }
        orders[line] = order;
        if (operation == "buy") {
            book[order.price].first += amount;
            total_buy += amount;
        } else {
            book[order.price].second += amount;
            total_sell += amount;
        }
    }

    long long best_volume = -1;
    int best_price = 0;
    long long buy_volume = total_buy;
    long long sell_volume = 0;
    for (map<int, pair<long long, long long> >::iterator it = book.begin(); it != book.end(); ++it) {
        if (it->second.first == 0 && it->second.second == 0) {
            continue;
        }
        sell_volume += it->second.second;
        long long volume = min(buy_volume, sell_volume);
        if (volume >= best_volume) {
            best_volume = volume;
            best_price = it->first;
        }
        buy_volume -= it->second.first;
    }

    if (best_volume < 0) {
        best_volume = 0;
    }
    cout << best_price / 100 << '.' << setw(2) << setfill('0') << best_price % 100;
    cout << ' ' << best_volume << '\n';
    return 0;
}

复杂度

设有效报价种类数为 $q$ ，记录条数为 $L$ 。维护订单和排序报价需要 $O(L\log L)$ 时间，扫描报价为 $O(q)$ ，空间复杂度为 $O(L)$ 。

总结

集合竞价的关键是把“价格阈值”转成前缀和与后缀和。撤单只改变有效订单状态，整数分表示保证了比较和输出都准确。

目录

形式化题目

思路

前缀量扫描

代码

复杂度

总结