YeungYeah 的乱写地

CCF201412-3 集合竞价

 Posts  

Problem

问题描述

某股票交易所请你编写一个程序，根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。
该程序的输入由很多行构成，每一行为一条记录，记录可能有以下几种：

  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。

Solution

核心思路

分析问题，需要找出使成交量最大的开盘价，我们只需遍历所有的价格，找出其中成交量最大的即可。所有可能的价格集合，其实就是买卖记录中出现的价格，结合输入的行数不超过5000，规模不大，直接暴力算出就行，看上去很简单。然而，这道题却搞了我一个晚上，提交过程一波三折，分数从30到50，再到90，最后才AC。

版本迭代

30分版本

在有了上面算法的大体思路后，主要的实现其实就是读取输入，存取买卖记录，根据记录撤销记录。一开始，我使用的是两个数组来分别存储买卖交易记录，然后用一个whole的数组来记录第i条记录在哪里，当要撤销记录时，才whole数组找到记录实际位置并取消。

提交后提示运行错误，30分

50分版本

分析30分版本的代码，会出现运行错误，无非是撤销记录出了问题，修改测试用例，加入了多条撤销指令，运行结果异常，撤销了非指定的记录。仔细分析后，发现问题在于，我通过whole数组来存储要撤销的指令在哪个数组（买还是卖）以及其索引，但在撤销指令删除某一条记录后，记录在买卖数组中的索引**可能（当要撤销的记录前有已经被撤销的记录）**会发生变化，而这种索引的变化并没有更新到whole数组，所以会导致撤销了错误的记录，甚至导致索引越界的错误。

于是，考虑直接重写这部分的代码，这次我放弃了此前的一次循环一步到位读取输入，直接变成了三步：

  1. 读取输出，添加到数组
  2. 根据撤销指令撤销相关的指令：这里我是直接将要撤销的指令和撤销指令本身设为None
  3. 将指令去除None后分开为buy和sell数组，存储买卖记录

但在实现撤销记录的过程中，又想到了另一个问题：如果我撤销的记录是一条撤销记录呢？纠结了一下好不好发生这种情况，回去细看问题描述，cancel也是一种记录，而cancel i的作用是撤销第i条记录。所以说，这种情况是有可能出现的。撤销了撤销记录的效果会怎样呢？按照字面意思来说，撤销第i行的记录，就应该是cancel记录无效了，为此，想到了一个比较巧妙的实现方法，将上面的第二步改为倒序遍历记录，实现撤销记录。

提交后错误，50分

90分版本

上面只有50分，非常的奇怪，内心觉得应该是上面纠结的撤销撤销记录的问题。改了一下，待撤销的记录是撤销记录的话就不撤销了，重新提交后，90分，说明前面关于撤销 cancel 记录的理解是错的。很是难受，难受不是因为说这一题错了，卡住了我，更关键的是，我这个理解是认真读题目描述，仔细分析字面意思，完完全全是根据题目得出来的理解，这也错了。上网搜了一圈，发现大多数人也是在吐槽这个设定。也算是一个自我安慰？

100分版本

分析上面的代码，还有10分丢在了哪里？通常错一个用例来说，都是卡在了特殊用例上面，有什么特殊用例呢？会不会是没有成交量？但很快就否定了，如果成交量为0，那里价格就可以取到无限高了（因为多个价格取值成交量相同时，取最高价格）。翻了一下别人的代码，发现有人直接用了浮点数也过了，但是我考虑到精度的问题，选择的是将读取的浮点数乘以100再转成整数处理，最后输出再转回去。于是我修改了测试用例，加入了一条两位小数的记录，果然输出异常了，当我输入一条价格为10.12的记录时，浮点数读取是 10.12，乘以 100 后却变成了 1011.99999999 而不是设想的 1012.0，然后还是直接取整，出事了。改成直接浮点数后，AC了，将取整改成 round 也能过。

最终AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

buy = []
sell = []
records = []
try:
    while True:
        inp = input()
        records.append(inp)
except EOFError:
    pass

i = len(records)-1
while i>=0:
    r = records[i]
    if r and r.startswith('cancel'):
        row = int(r.split()[1])-1
        if not records[row].startswith('cancel'):
            records[row]=None
        records[i]=None
    i-=1

records = filter(None,records)
for r in records:
    r = r.split()
    price,count = float(r[1]),int(r[2])
    if r[0]=='buy':
        buy.append((price,count))
    else:
        sell.append((price,count))

all_prices = [i[0] for i in sell]
all_prices.extend([i[0] for i in buy])
all_prices = set(all_prices)
ans_price,ans_count = 0,0
for price in all_prices:
    buy_count,sell_count=0,0
    for p,c in buy:
        if p>=price:buy_count+=c
    for p,c in sell:
        if p<=price:sell_count+=c
    count = min(buy_count,sell_count)
    if count>ans_count:ans_price,ans_count=price,count
    elif count==ans_count:ans_price=max(ans_price,price)

print('%.2f'%(ans_price),ans_count)

提交结果如下图（中间的C++实现是测试网上其它人的代码

相关文章：