問(wèn)題鏈接：CCF201412試題。

問(wèn)題描述：

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

程序說(shuō)明：（略）。

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

/* CCF201412-3 集合競(jìng)價(jià) */#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));    // 輸入數(shù)據(jù)    int no = 0, tno;    while(cin >> strading) {        if(strading[0] == 'c') {            // 設(shè)置交易號(hào)            no++;            // 輸入取消的交易號(hào)            cin >> tno;            // 設(shè)置取消標(biāo)志            cancelflag[tno] = true;        } else if(strading[0] == 'b' || strading[0] == 's') {            // 設(shè)置交易號(hào)            t.orderno = ++no;            // 輸入交易價(jià)格和數(shù)量            cin >> t.price >> t.quantity;            // 將交易分別放入買(mǎi)入和賣(mài)出的優(yōu)先隊(duì)列            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;    }    // 集合競(jìng)價(jià)處理    t.price = 0;    t.quantity = 0;    trading b, s;    for(;;) {        // 清除被取消的訂單（同時(shí)將隊(duì)頭放在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;        }        // 買(mǎi)賣(mài)隊(duì)列只要有一個(gè)為空，則處理結(jié)束        if(buy.empty() || sell.empty())            break;        // 集合競(jìng)價(jià)處理        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;    }    // 輸出結(jié)果    printf("%.2f", t.price);    cout << " " << t.quantity << endl;    return 0;}/*測(cè)試樣例：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*/