因为参加*CTF，鸽了两天的算法。
day 06
题目描述
“饱了么”外卖系统中维护着N 家外卖店，编号1~N。
每家外卖店都有一个优先级，初始时(0 时刻) 优先级都为0。
每经过1 个时间单位，如果外卖店没有订单，则优先级会减少1，最低减到0；
而如果外卖店有订单，则优先级不减反加，每有一单优先级加2。
如果某家外卖店某时刻优先级大于5，则会被系统加入优先缓存中；
如果优先级小于等于3，则会被清除出优先缓存。
给定T 时刻以内的M 条订单信息，请你计算T 时刻时有多少外卖店在优先缓存中。
输入
第一行包含3 个整数N、M 和T。
以下M 行每行包含两个整数ts 和id，表示ts 时刻编号id 的外卖店收到一个订单
1<=N, M, T<=100000，1<=ts<=T，1<=id<=N。
输出
输出一个整数代表答案。
样例输入
1
2
3
4
5
6
7
| 2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
|
样例输出
题目分析
根据题目含义，顺着做下来，没有什么费解的地方，但是限制时间，用python就就很难去AC
用dict存储每个外卖店的优先级和订单的时间以及外卖店编号
1
2
3
4
5
| for i in range(1, 100000): # 第i时刻，外卖店订单
order[i] = []
shop = dict()
for i in range(N): #外卖店的优先级存储
shop[i] = 0
|
然后每一时间遍历，顺着题目思路下来就ok
题解
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
|
N, M, T = input().split(' ')
order = dict()
N, M, T = eval(N), eval(M), eval(T)
for i in range(1, 100000): # 第i时刻，外卖店订单
order[i] = []
shop = dict()
for i in range(N): #外卖店的优先级存储
shop[i] = 0
priority = []
for i in range(M):
ts_, id_ = input().split(' ')
order[eval(ts_)].append(eval(id_))
for i in range(1, T+1):
for j in range(N):
if j in order[i]:
shop[j] += 2
if shop[j] > 5:
priority.append(j)
else:
shop[j] -= 1 if shop[j] > 0 else 0
if j in priority and shop[j] < 3:
del priority[priority.index(j)]
print(len(priority))
|