参考了http://blog.csdn.net/accelerator_2016/article/details/52798308 的思路,它的代码是C++,是可以AC的,我用Pyhon2写了遍,感觉做法是一样的,但是TLE,搞不懂是什么原因,来求助一番T.T
代码:
import Queue
def register(pq, students, n, m, k):
end_time = [0 for i in range(m)]
rst = [0 for i in range(n)]
while pq.qsize() != 0:
i += 1
serve = pq.get()
end_time[serve[2]] = max(serve[0], end_time[serve[2]]) + students[serve[4]][2][serve[3]]
if serve[3] != students[serve[4]][0] - 1:
pq.put([end_time[serve[2]] + k, serve[1], students[serve[4]][1][serve[3]+1], serve[3]+1, serve[4]])
else:
rst[serve[4]] = end_time[serve[2]]
return rst
def main():
line = [int(x) for x in raw_input().strip().split()]
n, m, k = line[0], line[1], line[2]
students = []
pq = Queue.PriorityQueue()
for i in range(n):
line = [int(x) for x in raw_input().strip().split()]
s, t, p = line[0], line[1], line[2]
order = []
time = []
index = 3
for j in range(p):
order.append(line[index]-1)
time.append(line[index+1])
index += 2
students.append([p, order, time])
pq.put([t + k, s, order[0], 0, i])
rst = register(pq, students, n, m, k)
for r in rst:
print r
if __name__ == '__main__':
main()