1934. 贝茜放慢脚步
摘要
Title: 1934. 贝茜放慢脚步
Tag: 二路归并
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1934. 贝茜放慢脚步
-
题意
-
思路
思路就是二路归并，即归并排序中的归并步骤
将时刻和路程点分别排序，组成两个数组，像是归并排序一般，判断这两个数组中的最小值哪个最先拿出，最后拿完两个数组中的值即可注意
- 速度存的是倒数，这样利于更新
- 有可能结尾不是1000，所以路程点数组要加上结尾
-
代码
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
29
30
31
32
33
34
35
36
37'''
Author: NEFU AB-IN
Date: 2022-01-18 12:50:31
FilePath: \ACM\Acwing\1934.py
LastEditTime: 2022-02-18 20:18:50
'''
a = [] #时间
b = [] #路程
if __name__ == "__main__":
n = int(input())
for i in range(n):
op, x = input().split()
x = int(x)
if op == 'T':
a.append(x)
else:
b.append(x)
b.append(1000) #添加终点
a.sort()
b.sort()
t, s, v = 0, 0, 1 #v时速度的倒数
i, j = 0, 0
while i < len(a) or j < len(b):
if j == len(b) or i < len(a) and a[i] - t < (b[j] - s) * v:
s += (a[i] - t) / v
t = a[i]
v += 1
i += 1
else:
t += (b[j] - s) * v
s = b[j]
v += 1
j += 1
print(round(t))
