hduoj4311

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4311
题解：

array1 = [(-4, -1),
          (-1, -2),
          (2, -4),
          (0, 2),
          (0, 3),
          (5, -2)]
array2 = [(0, 0),
          (2, 0),
          (-5, -2),
          (2, -2),
          (-1, 2),
          (4, 0)]
array3 = [(-5, 1),
          (-1, 3),
          (3, 1),
          (3, -1),
          (1, -1)]
array4 = [(-1, -1),
          (-3, 2),
          (-4, 4),
          (5, 2),
          (5, -4),
          (3, -1),
          (4, 3),
          (-1, -2),
          (3, 4),
          (-2, 2)]


def cal_min_sum(_array: list):
    sum_dict = {}
    _array.sort()
    now_sum = sum([abs(a - _array[0]) for a in _array])
    sum_dict[_array[0]] = now_sum
    for i in range(1, len(_array)):
        # left_inc = abs(_array[i - 1] - _array[i]) * (i + 1)
        # right_dec = abs(_array[i - 1] - _array[i]) * (len(_array) - i + 1)
        # now_sum = now_sum - right_dec + left_inc
        # 化简：(-len(_array) + 2*i)
        now_sum = now_sum + abs(_array[i - 1] - _array[i]) * (2 * i - len(_array))
        sum_dict[_array[i]] = now_sum
    return sum_dict


def resolve(_array: list):
    x_dict = cal_min_sum([a[0] for a in _array])
    y_dict = cal_min_sum([a[1] for a in _array])
    total_sum = min([x_dict[a[0]] + y_dict[a[1]] for a in _array])
    return total_sum


def test_resolve():
    assert resolve(_array=array1) == 26
    assert resolve(_array=array2) == 20
    assert resolve(_array=array3) == 20
    assert resolve(_array=array4) == 56


if __name__ == '__main__':
    test_resolve()