题目链接:
计算机软件能力认证考试系统http://118.190.20.162/view.page?gpid=T91
【思路】因为最后取的时候是按照全部商品的优先级来,所以我把商品类别和商品编号合并成一个键,str(type)+'#'+str(id),值就是商品的得分,这样就可以把他们存在同一个字典中了,这样添加和删除都是O(1)。
查询的时候首先对字典中的元素进行自定义规则的排序,排序的复杂度为O(nlogn)比较高,所以定义一个变量记录上次排序后是否进行了插入或删除操作,只有操作过才重新排序。最后,记录总个数k和每类商品的个数,按照题目给的个数输出。
但是。。超时了,只能拿10分。
from functools import cmp_to_key
def cmp(a, b):
if a[1] < b[1]:
return 1
elif a[1] == b[1]:
p1, q1 = [int(i) for i in a[0].split('#')]
p2, q2 = [int(i) for i in b[0].split('#')]
if p1 > p2:
return 1
elif p1 == p2:
if q1 > q2:
return 1
return -1
m, n = [int(i) for i in input().split()]
goods = {}
for _ in range(n):
a, b = [int(i) for i in input().split()]
for i in range(m):
key = str(i) + '#' + str(a)
goods[key] = b
tmp = sorted(goods.items(), key=cmp_to_key(cmp))
p = int(input())
modify = 0
for _ in range(p):
op = [int(i) for i in input().split()]
type = op[0]
if type == 1:
modify = 1
key = str(op[1]) + '#' + str(op[2])
goods[key] = op[3]
elif type == 2:
modify = 1
key = str(op[1]) + '#' + str(op[2])
goods.pop(key)
else:
if modify == 1:
modify = 0
tmp = sorted(goods.items(), key=cmp_to_key(cmp))
# print(tmp)
k = op[1]
cnt = [0] * m
res = [[] for i in range(m)]
num = 0
for i in range(2, len(op)):
if op[i] > 0:
num += 1
cnt[i - 2] = op[i]
i = 0
while i < k:
good = tmp[i]
a, b = [int(j) for j in good[0].split('#')]
if cnt[a] > 0:
res[a].append(b)
cnt[a] -= 1
if cnt[a] == 0:
num -= 1
if num == 0:
break
i += 1
for i in res:
if len(i) == 0:
print(-1)
else:
for j in range(len(i)):
if j == len(i) - 1:
print(i[j])
else:
print(i[j], end=' ')