?

---

問題如下： 某股票交易所請你編寫一個程序，根據(jù)開盤前客戶提交的訂單來確定某特定股票的開盤價和開盤成交量。
　　該程序的輸入由很多行構(gòu)成，每一行為一條記錄，記錄可能有以下幾種：
　　1. buy p s 表示一個購買股票的買單，每手出價為p，購買股數(shù)為s。
　　2. sell p s 表示一個出售股票的賣單，每手出價為p，出售股數(shù)為s。
　　3. cancel i表示撤銷第i行的記錄。
　　如果開盤價為p₀，則系統(tǒng)可以將所有出價至少為p₀的買單和所有出價至多為p₀的賣單進行匹配。因此，此時的開盤成交量為出價至少為p₀的買單的總股數(shù)和所有出價至多為p₀的賣單的總股數(shù)之間的較小值。
　　你的程序需要確定一個開盤價，使得開盤成交量盡可能地大。如果有多個符合條件的開盤價，你的程序應(yīng)當輸出最高的那一個。 輸入格式 輸入數(shù)據(jù)有任意多行，每一行是一條記錄。保證輸入合法。股數(shù)為不超過10⁸的正整數(shù)，出價為精確到恰好小數(shù)點后兩位的正實數(shù)，且不超過10000.00。 輸出格式 你需要輸出一行，包含兩個數(shù)，以一個空格分隔。第一個數(shù)是開盤價，第二個是此開盤價下的成交量。開盤價需要精確到小數(shù)點后恰好兩位。 樣例輸入 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 樣例輸出 9.00 450 評測用例規(guī)模與約定 對于100%的數(shù)據(jù)，輸入的行數(shù)不超過5000。

---

源碼： #include "stdafx.h" #include <iostream> #include <string.h> #include <algorithm> using namespace std;const int MIN = 0;typedef struct Shares{//買或賣的價格double price;//股數(shù)int number;//false 表示買//true 表示賣bool buyOrSell;//是否被cancelbool enable;Shares(){price = 0.00;number = 0;buyOrSell = false;enable = true;} }; int min(int num1, int num2); //取消的第th條交易股 void cancelRecord(int th); //從未分類的交易股，按照條件進行分類存儲，并進行排序 void divTypeOfShares(int n, int &lenOfSell, int& lenOfBuy); //計算結(jié)果 void computePriceAndMax(int n, double& perPrice, int& perNumber);//存儲輸入的交易股，不區(qū)分買家還是賣家 Shares shares[10001]; //存儲買家的交易股 Shares sharesBuy[5001]; //存儲賣家的交易股 Shares sharesSell[5001];//定義買家類型的交易股比較函數(shù)，用于排序 //主排序按照價格為關(guān)鍵字遞增 //次排序按照購買股數(shù)作為關(guān)鍵字遞減 bool cmpBuy(Shares buy1, Shares buy2) {if (buy1.price != buy2.price)return buy1.price < buy2.price;else if (buy1.price == buy2.price)return buy1.number >= buy2.number; }//賣家類型的交易股同上 bool cmpSell(Shares sell1, Shares sell2) {if (sell1.price != sell2.price)return sell1.price >= sell2.price;else if (sell1.price == sell2.price)return sell1.number >= sell2.number; }void main(void) {char typeOfShares[10];double price;int number;int index = 1;double perPrice = 0.00;int perNumber = MIN;while (cin >> typeOfShares){if (strcmp(typeOfShares, "buy") == 0){cin >> price >> number;shares[index].buyOrSell = false;shares[index].price = price;shares[index].number = number;index++;}else if (strcmp(typeOfShares, "sell") == 0){cin >> price >> number;shares[index].buyOrSell = true;shares[index].price = price;shares[index].number = number;index++;}else if (strcmp(typeOfShares, "cancel") == 0){int recordth;cin >> recordth;cancelRecord(recordth);}else{computePriceAndMax(index - 1, perPrice, perNumber);cout << perPrice << ' ' << perNumber << endl;}memset(typeOfShares, 0, 10);} }int min(int num1, int num2) {if (num1 <= num2)return num1;elsereturn num2; }//取消的第th條交易股 void cancelRecord(int th) {shares[th].price = 0.00;shares[th].number = 0;shares[th].enable = false; }//從未分類的交易股，按照條件進行分類存儲，并進行排序 void divTypeOfShares(int n, int &lenOfSell, int& lenOfBuy) {int i = 1, j = 0, k = 0;for (; i <= n; i++){if (shares[i].buyOrSell == false && shares[i].enable == true)sharesBuy[j++] = shares[i];else if (shares[i].buyOrSell == true && shares[i].enable == true)sharesSell[k++] = shares[i];}lenOfBuy = j;lenOfSell = k;sort(sharesBuy, sharesBuy + lenOfBuy, cmpBuy);sort(sharesSell, sharesSell + lenOfSell, cmpSell); }void computePriceAndMax(int n, double& perPrice, int& perNumber) {double tmpPrice;//臨時存儲最優(yōu)的開盤價int sumBuy = 0, sumSell = 0;//買的總股數(shù)和賣的總股數(shù)int lenOfSharesBuy, lenOfSharesSell;//買家類型數(shù)組長度，賣家類型數(shù)組長度 divTypeOfShares(n, lenOfSharesSell, lenOfSharesBuy);for (int i = 0; i < lenOfSharesBuy; i++){/*由前面的買家交易股的排序知道當前的交易股，其價格是大于等于其前面的交易股的。那么如果它的股數(shù)比前面所有的交易股之和大或者相等，則無需購買前面的交易股。*/if (sharesBuy[i].number > sumBuy){tmpPrice = sharesBuy[i].price;sumBuy = sharesBuy[i].number;}elsesumBuy += sharesBuy[i].number;sumSell = 0;for (int j = 0; j < lenOfSharesSell; j++){//如果當前的賣家股的價格比開盤價高，則不能購買，跳過if (sharesSell[j].price > tmpPrice)continue;sumSell += sharesSell[j].number;}if (perNumber <= min(sumBuy, sumSell)){perNumber = min(sumBuy, sumSell);perPrice = tmpPrice;}} }

?

總結(jié)

以上是生活随笔為你收集整理的股票开盘的最大成交额-----一道不错的贪心算法题目的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。