2 条题解

  • 0
    @ 2025-10-13 20:50:57

    哈基米南北路多

    结论在下面帆学长的题解里,形象的说,可以把这些点的纵坐标放进一条一维轴中,指定一个点,则曼哈顿距离则是这些点到指定点的距离和,那么这个点定在最左点和最右点之间(因为超出范围产出的多余距离一定会导致结果不是最优解) 下面看两种情况 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
    上传者