CCF 201709-2 公共钥匙盒 python 满分
题目叙述问题描述：略输入格式：略输出格式：略样例
满分证明解题思路基础版大佬版
满分代码基础版大佬版
感谢及参考博文
题目叙述
问题描述：略
输入格式：略
输出格式：略
样例
样例输入
5 2
4 3 3
2 2 7
样例输出
1 4 3 2 5
样例说明
第一位老师从时刻
3开始使用
4号教室的钥匙，使用
3单位时间，所以在时刻
6还钥匙。
第二位老师从时刻
2开始使用钥匙，使用
7单位时间，所以在时刻
9还钥匙。
每个关键时刻后的钥匙状态如下（X表示空）：
时刻
2后为
1X345；
时刻
3后为
1X3X5；
时刻
6后为
143X5；
时刻
9后为
14325。
样例输入
5 7
1 1 14
3 3 12
1 15 12
2 7 20
3 18 12
4 21 19
5 30 9
样例输出
1 2 3 5 4
满分证明
解题思路
基础版
分别按借还的时间从小到大排序；取出最大时间作为遍历使用；同一时间先还后借。
大佬版
按照时间线来处理；直接存的时候，进行处理；标记是借还是取。
满分代码
基础版
n
, k
= map(int, input().split())
ss
= [list(map(int, input().split())) for _ in
range(k
)]
# 直接改为还的时间
for i in
range(k
):
ss
[i
][2] = ss
[i
][1] + ss
[i
][2]
# 保证同时还，按从小到大顺序
ss
.sort()
ke
= list(range(1, n
+ 1))
j
= sorted(ss
, key
=lambda x
: (x
[1]))
h
= sorted(ss
, key
=lambda x
: (x
[2]))
max
= sorted(list(set(list(map(lambda x
: (x
[1]), j
)) + list(map(lambda x
: (x
[2]), h
)))))
j_index
= 0
h_index
= 0
for m in max
:
# 同一时刻先还后借
while m in
list(map(lambda x
: (x
[2]), h
)):
teml
= ke
.index(0)
ke
[teml
] = h
[h_index
][0]
h
[h_index
][2] = -1
h_index
+= 1
while m in
list(map(lambda x
: (x
[1]), j
)):
tem
= j
[j_index
][0]
id
= ke
.index(tem
)
ke
[id
] = 0
j
[j_index
][1] = -1
j_index
+= 1
for i in
range(n
):
print(ke
[i
], end
=" ")
大佬版
n
, k
= map(int, input().split())
fn
= list(range(1, n
+ 1))
ss
= []
for _ in
range(k
):
w
, s
, c
= map(int, input().split())
ss
.append([s
, True
, w
])
ss
.append([s
+ c
, False
, w
])
ss
.sort()
for t
, flag
, k in ss
:
if flag
:
fn
[fn
.index(k
)] = 0
else:
fn
[fn
.index(0)] = k
for i in
range(n
):
print(fn
[i
], end
=" ")
感谢及参考博文
部分内容参考以下链接，这里表示感谢 Thanks♪(･ω･)ﾉ 参考博文1 201709-2 python CCF 更简单的思路和代码 100分 https://blog.csdn.net/CarterYang0/article/details/103747699
