1902. 马拉松
摘要
Title: 1902. 马拉松
Tag: 模拟
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1902. 马拉松
-
题意
见原题
-
思路
去除一个点，使得距离最小
那就先将间隔数组存下来，再存一个去除掉每个检查点的间隔数组，比较一下最优去除方案即可 -
代码
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'''
Author: NEFU AB-IN
Date: 2022-04-13 10:56:49
FilePath: \ACM\Acwing\1902.py
LastEditTime: 2022-04-13 10:56:50
'''
def cale(p, q):
return abs(p[0] - q[0]) + abs(p[1] - q[1])
n = int(input())
a = [] #原数组
b = [] #间隔数组
c = [] #去除的间隔数组
for i in range(n):
x, y = map(int, input().split())
a.append([x, y])
for i in range(1, n):
b.append(cale(a[i], a[i - 1]))
for i in range(2, n):
c.append(cale(a[i], a[i - 2]))
ans, cnt, tmp = sum(b), sum(b), sum(b)
for i in range(len(c)):
cnt -= (b[i] + b[i + 1])
cnt += c[i]
ans = min(ans, cnt)
cnt = tmp
print(ans)