CCF 2014-12-3 集合竞价 100分_综合

试题编号：	201412-3
试题名称：	集合竞价
时间限制：	1.0s
内存限制：	256.0MB
问题描述：	问题描述　　某股票交易所请你编写一个程序，根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。　　该程序的输入由很多行构成，每一行为一条记录，记录可能有以下几种：　　1. buy p s 表示一个购买股票的买单，每手出价为p，购买股数为s。　　2. sell p s 表示一个出售股票的卖单，每手出价为p，出售股数为s。　　3. cancel i表示撤销第i行的记录。　　如果开盘价为p0，则系统可以将所有出价至少为p0的买单和所有出价至多为p0的卖单进行匹配。因此，此时的开盘成交量为出价至少为p0的买单的总股数和所有出价至多为p0的卖单的总股数之间的较小值。　　你的程序需要确定一个开盘价，使得开盘成交量尽可能地大。如果有多个符合条件的开盘价，你的程序应当输出最高的那一个。输入格式　　输入数据有任意多行，每一行是一条记录。保证输入合法。股数为不超过108的正整数，出价为精确到恰好小数点后两位的正实数，且不超过10000.00。输出格式　　你需要输出一行，包含两个数，以一个空格分隔。第一个数是开盘价，第二个是此开盘价下的成交量。开盘价需要精确到小数点后恰好两位。样例输入 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 评测用例规模与约定　　对于100%的数据，输入的行数不超过5000。

#include<iostream>
#include<algorithm>
using namespace std;typedef struct Node{string type;double p;int num;
}Node; Node rec[5001],buy[5001],sell[5001];bool cmp_buy(Node a,Node b){return a.p>b.p;
}bool cmp_sell(Node a,Node b){return a.p<b.p;
}
int main(){string str;double p;int num,n=0,bn=0,sn=0;while(cin>>str){if(str!="cancel"){cin>>rec[n].p>>rec[n].num;rec[n].type=str;n++;}else{int del;cin>>del;rec[n].type=str;rec[n].num=del;n++;}}for(int i=n-1;i>=0;i--){if(rec[i].type=="cancel"){if(rec[rec[i].num-1].type!="cancel"){//注意！！！cancel不能取消cancel，只能取消buy或sell rec[rec[i].num-1].type="";}}else if(rec[i].type=="buy"){buy[bn]=rec[i];bn++;}else if(rec[i].type=="sell"){sell[sn]=rec[i];sn++;}}sort(rec,rec+n,cmp_buy);//总记录按出价从大到小 sort(buy,buy+bn,cmp_buy);//购买记录按出价从大到小 sort(sell,sell+sn,cmp_sell);//卖出记录按出价从小到大 double p0,suc_p;long long buy_num=0,sell_num=0,temp_num=0,suc_num=0;for(int i=0;i<n;i++){//对总记录所有的出价遍历 if(rec[i].p==0)break;buy_num=0;sell_num=0;p0=rec[i].p;for(int j=0;j<bn;j++){//获取出价的总买入量 if(buy[j].p<p0)break;else buy_num+=buy[j].num;}for(int j=0;j<sn;j++){//获取出价的总卖出量 if(sell[j].p>p0)break;else sell_num+=sell[j].num;}if(sell_num>buy_num)temp_num=buy_num;else temp_num=sell_num;if(temp_num>suc_num){suc_num=temp_num;suc_p=p0;}}printf("%.2f %lld",suc_p,suc_num);
}

更多相关CCF的试题解答，请点击>>CCF历年认证考试解答