#7103. 选址问题

选址问题

题目描述

在一条直线上,有 nn 个人,其中第 ii 个人在直线上的坐标为 xix_i

请在直线上,找到一个聚会点,聚会点可以在直线的任何位置上,使得所有人到达这个聚会点的路程之和达到最小。输出这个最小值。

输入格式

  • 单个整数:表示 nn
  • nn 个整数:表示 x1x_1xnx_n

输出格式

5
3 1 4 1 5
7

数据范围

  • 30%30\% 的数据,1n1001\leq n\leq 100
  • 60%60\% 的数据,1n5,0001\leq n\leq 5,000
  • 100%100\% 的数据,1n100,0001\leq n\leq 100,000
  • 20,000xi20,000-20,000\leq x_i\leq 20,000