CCF CSP认证历年题目自练 Day40

题目

试题编号： 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。

题目分析（个人理解）

1. 第一次见这种输入，没有限制条件，只是行数不能超过5000，那就是类似前缀和的思想，可以理解为输入多少行操作我每一步都要求出开盘价和成交量。
2. 对于存储结构还是选择先用列表存储，为什么？因为有个叫cancel的操作是将指定顺序的操作删除，那么最方便的一定是列表了，又因为数据记录不只一条，那么就用二位列表存储，第一维度表示每个记录，第二维度表示每个记录的三个参数（操作，出价，股数）存好之后先判断第一个字符串是否是cancel，如果是就删除此纪录（删除自己）和指定的记录。感觉有点像做数据的预处理，删完之后就是干净的数据了，如何具体实现？
3. 可以直接将cancel标记为-1，将cancel指定要删除的操作的第一个字符串替换为-1，然后遍历整个二维列表，如果第一维度的第1个参数值是-1，就将整条记录从二维列表删除即可。难点来了，再看对于开盘价的定义：如果开盘价为p0，则系统可以将所有出价至少为p0的买单和所有出价至多为p0的卖单进行匹配。此时的开盘成交量为出价至少为p0的买单的总股数和所有出价至多为p0的卖单的总股数之间的较小值。核心算法是：对于buy需要求所有小于当前出价的所有股数和，对sell需要求所有大于当前出价的所有股数和，然后取两个股数和的最小值作为当前成交量，遍历每一个出价，找到每一个成交量，将最大的成交量作为最终成交量，此时的出价作为开盘价，输出即可。
4. 如何具体实现？首先肯定涉及到排序的问题，我先把清理之后的二维列表以出价的从高到低的顺序（用sorted函数和lambda函数实现）从从新排序并更新列表。然后创建两个字典，一个是字典sell,将出价作为字典的键，将小于当前sell的出价的总股数作为字典的值，用倒序遍历二维列表；此时字典的键是按照从小到大的顺序排列。另一个字典buy，顺序遍历列表，将出价作为字典的键，将大于当前buy的出价的总股数作为字典的值。此时字典的键是按照从大到小的顺序排列。
5. 一切都记录好了，下面就是判断环节，判断每一个当前出价buy的成交量和sell的成交量，找到最小成交量作为当前出价的成交量，然后将这些记录的成交量中的最大值找出来作为最终成交量，此时的出价就是开盘价！
6. 上代码！！！

import sys
record=[]
strike=[]
for s in sys.stdin:record.append(list(s.split()))#将记录写入record二维列表
for i in record:if i[0]=='cancel':i[0]=-1record[int(i[1])-1][0]=-1#将要删除的记录的第一个字符串设置为-1else:i[1]=float(i[1])i[2]=int(i[2])
for i in record[::-1]:#清理二维列表if i[0]==-1:record.remove(i)
record.sort(key=lambda x:x[1],reverse=True)#按照出价将所有的buy和sell从高到低排序
sell={}
num=0#计算sell总股数
for x,y,z in record[::-1]:#对于sell是小于开盘价的总股数if x=='sell':num+=z#将总股数用num记录sell[y]=num#将出价作为字典的键，将小于当前sell的出价的总股数作为字典的值，#此时字典的键是按照从小到大的顺序排列
buy={}
num=0#计算buy总股数
for x,y,z in record:#对buy是大于开盘价的总股数if x=='buy':num+=z#计算总股数buy[y]=num#此时字典的键是按照从大到小的顺序排列
num=0#成交量
price=0#开盘价
for i in record:if min(sell[i[1]],buy[i[1]])>num:#找到较小值作为当开盘价是i[1]时的开盘成交量，# 遍历所有i[1]找到最大成交量,确定此i[1]是最终开盘价price=i[1]#此时的值就是开盘价num=min(sell[i[1]],buy[i[1]])#当前i[1]作为开盘价的成交量
print("%.2f %d"%(price,num))

总结

我从未止步。-----szy2023.10.28