历年题解 CCF CSP历年题解（python）

样例输入：

5 2
4 3 3
2 2 7

5 7
1 1 14
3 3 12
1 15 12
2 7 20
3 18 12
4 21 19
5 30 9

题目链接：201709-2公共钥匙盒

问题分析：
建立一个时间列表，将取、存都按时间从小到大排序，记录钥匙编号，时间相同时，先放回钥匙后取出钥匙，取按钥匙编号从小到大
使用第一个样例输入
out=[[2, 2], [4, 3], [0, 11000]]
put=[[4, 6], [2, 9], [0, 11000]]
t=[2, 4, 4, 2]
即整个顺序为先将2号钥匙取出，再将4号钥匙取出，再将4号钥匙放回，最后将2号钥匙放回

满分例程：

N,K=map(int,input().split())
y=[]
for i in range(1,N+1):#初始状态钥匙盒
    y.append(i)
out=[[0,11000]]#取出钥匙    [0,11000]防止数组越界,或在排序后out、put后添加
put=[[0,11000]]#放入钥匙    取题目给定out=[[0,10001]]put=[[0,10101]]模拟是70分
for i in range(K):
    w,s,c=map(int,input().split())
    out.append([w,s])
    put.append([w,s+c])
#out.sort(key=lambda x:x[0])取出未要求：多位老师同时取钥匙，按钥匙编号从小到大的顺序取
out.sort(key=lambda x:x[1])#按时间排序
put.sort(key=lambda x:x[0])#有多位老师同时还钥匙，按钥匙编号从小到大的顺序还
put.sort(key=lambda x:x[1])#按时间排序

o,p=0,0#分别是取出、放入钥匙的索引
t=[]#时间线列表
for i in range(2*K):
    #时间小的优先或者时间相同时存钥匙优先
    if out[o][1]>=put[p][1]:
        t.append(put[p][0])
        p+=1
    else:
        t.append(out[o][0])
        o+=1
for i in t:
    if i in y:#有该编号钥匙即取钥匙
        for j in range(N):
            if y[j]==i:
                y[j]=0
                break
    else:#没用该编号钥匙即存钥匙
        for j in range(N):
            if y[j]==0:
                y[j]=i
                break
print(y[0],end='')
for i in range(1,N):
    print('',y[i],end='')

#如果将程序中3到25行换为以下程序，模拟得分40分
#未考虑如果同一时刻既有老师还钥匙又有老师取钥匙，则老师们会先将钥匙全还回去再取出。
for i in range(1,N+1):
    y.append(i)
l=[]
for i in range(K):
    w,s,c=map(int,input().split())
    l.append([w,s])
    l.append([w,s+c])
l.sort(key=lambda x:x[0])
l.sort(key=lambda x:x[1])
t=[]
for i in l:
    t.append(i[0])