問題鏈接：CCF201412試題。

問題描述：

  某股票交易所請你編寫一個程序，根據開盤前客戶提交的訂單來確定某特定股票的開盤價和開盤成交量。  該程序的輸入由很多行構成，每一行為一條記錄，記錄可能有以下幾種：  1. buy p s 表示一個購買股票的買單，每手出價為p，購買股數為s。  2. sell p s 表示一個出售股票的賣單，每手出價為p，出售股數為s。  3. cancel i表示撤銷第i行的記錄。  如果開盤價為p0，則系統可以將所有出價至少為p0的買單和所有出價至多為p0的賣單進行匹配。因此，此時的開盤成交量為出價至少為p0的買單的總股數和所有出價至多為p0的賣單的總股數之間的較小值。  你的程序需要確定一個開盤價，使得開盤成交量盡可能地大。如果有多個符合條件的開盤價，你的程序應當輸出最高的那一個。  輸入數據有任意多行，每一行是一條記錄。保證輸入合法。股數為不超過108的正整數，出價為精確到恰好小數點后兩位的正實數，且不超過10000.00。  你需要輸出一行，包含兩個數，以一個空格分隔。第一個數是開盤價，第二個是此開盤價下的成交量。開盤價需要精確到小數點后恰好兩位。問題分析：這是一個競價匹配的問題。數據可以存儲在結構數組中，但未必是好的方案。使用兩個優先隊列，一個用于存儲購入訂單，按價格從大到小排列；另外一個用于存儲賣出訂單，按價格從小到大排列；然后進行價格的匹配處理。

程序說明：（略）。

提交后得100分的C++語言程序如下：

/* CCF201412-3 集合競價 */#include <iostream>#include <queue>#include <cstring>#include <cstdio>using namespace std;const int N = 5000;struct trading {    int orderno;    char t;    float PRice;    long long quantity;    bool Operator < (const trading& n) const {        if(t == 's')            return price > n.price;        else // t == 'b'            return price < n.price;    }};bool cancelflag[N+1];int main(){    trading t;    priority_queue<trading> sell, buy;    string strading;    // 變量初始化    memset(cancelflag, false, sizeof(cancelflag));    // 輸入數據    int no = 0, tno;    while(cin >> strading) {        if(strading[0] == 'c') {            // 設置交易號            no++;            // 輸入取消的交易號            cin >> tno;            // 設置取消標志            cancelflag[tno] = true;        } else if(strading[0] == 'b' || strading[0] == 's') {            // 設置交易號            t.orderno = ++no;            // 輸入交易價格和數量            cin >> t.price >> t.quantity;            // 將交易分別放入買入和賣出的優先隊列            if(strading[0] == 'b') {                t.t = strading[0];                buy.push(t);            } else {    // t.trading[0] == 's'                t.t = strading[0];                sell.push(t);            }        } else            break;    }    // 集合競價處理    t.price = 0;    t.quantity = 0;    trading b, s;    for(;;) {        // 清除被取消的訂單（同時將隊頭放在b和s中）        while(!buy.empty()) {            b = buy.top();            if(cancelflag[b.orderno])                buy.pop();            else                break;        }        while(!sell.empty()) {            s = sell.top();            if(cancelflag[s.orderno])                sell.pop();            else                break;        }        // 買賣隊列只要有一個為空，則處理結束        if(buy.empty() || sell.empty())            break;        // 集合競價處理        if(b.price >= s.price) {            t.quantity += min(b.quantity, s.quantity);            t.price = b.price;            if(b.quantity == s.quantity) {                buy.pop();                sell.pop();            } else if(b.quantity > s.quantity) {                b.quantity -= s.quantity;                buy.pop();                buy.push(b);                sell.pop();            } else {    // b.quantity < s.quantity                buy.pop();                s.quantity -= b.quantity;                sell.pop();                sell.push(s);            }        } else            break;    }    // 輸出結果    printf("%.2f", t.price);    cout << " " << t.quantity << endl;    return 0;}/*測試樣例：sell 8.88 100sell 8.88 175sell 9.00 400buy 8.88 400cancel 1sell 100.00 508.88 175buy 9.25 100buy 8.88 175buy 9.00 400sell 8.88 400cancel 1buy 100.00 509.00 400buy 9.25 100buy 8.88 175buy 9.00 400sell 8.79 1501cancel 1cancel 29.00 400buy 9.25 110buy 8.88 300buy 18.88 200sell 8.88 201sell 9.25 1009.25 301*/