2 条题解
-
0
哈基米南北路多
结论在下面帆学长的题解里,形象的说,可以把这些点的纵坐标放进一条一维轴中,指定一个点,则曼哈顿距离则是这些点到指定点的距离和,那么这个点定在最左点和最右点之间(因为超出范围产出的多余距离一定会导致结果不是最优解) 下面看两种情况 1.元素数量为奇数 将指定点设为在最中间的点可省去到此点的距离,而其他的点距离和即为从中间往两边数左右各一个数的距离之和 2.元素数量为偶数 大体和奇数情况一致,但目标点可以为中间两点之间的任意点,结果都是最优解不变
参考代码(python)
from sys import stdin,setrecursionlimit from math import inf,ceil,sqrt from collections import Counter,deque n,x=[int(_) for _ in stdin.readline().split()] d=[[int(_) for _ in stdin.readline().split()] for i in range(n)] d.sort(key=lambda x:x[1]) ans=sum(abs(x-d[i][0]) for i in range(n)) for i in range(n // 2): ans += d[n-i-1][1] - d[i][1] print(ans)
信息
- ID
- 1100
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 31
- 已通过
- 4
- 上传者