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

問(wèn)題描述：

  某股票交易所請(qǐng)你編寫一個(gè)程序，根據(jù)開盤前客戶提交的訂單來(lái)確定某特定股票的開盤價(jià)和開盤成交量。  該程序的輸入由很多行構(gòu)成，每一行為一條記錄，記錄可能有以下幾種：  1. buy p s 表示一個(gè)購(gòu)買股票的買單，每手出價(jià)為p，購(gòu)買股數(shù)為s。  2. sell p s 表示一個(gè)出售股票的賣單，每手出價(jià)為p，出售股數(shù)為s。  3. cancel i表示撤銷第i行的記錄。  如果開盤價(jià)為p0，則系統(tǒng)可以將所有出價(jià)至少為p0的買單和所有出價(jià)至多為p0的賣單進(jìn)行匹配。因此，此時(shí)的開盤成交量為出價(jià)至少為p0的買單的總股數(shù)和所有出價(jià)至多為p0的賣單的總股數(shù)之間的較小值。  你的程序需要確定一個(gè)開盤價(jià)，使得開盤成交量盡可能地大。如果有多個(gè)符合條件的開盤價(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ù)是開盤價(jià)，第二個(gè)是此開盤價(jià)下的成交量。開盤價(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ǔ)賣出訂單，按價(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;            // 將交易分別放入買入和賣出的優(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;        }        // 買賣隊(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*/