10057专题

UVA 10057 中位数

题目 给出N个数,求出其中一个数A,所有数与这个数的差的绝对值之和最小。 这个数必须是中位数。 假设N是奇数,对于中位数MID,左边有N/2个数,右边有N/2个数。假设此时和为SUM。 如果A不选择MID,而是选择MID左边一个数的话,则左边的数到A的距离均减一,右边的数加上中位数到MID距离加一。SUM‘=SUM+1,SUM增大,同理右边。 所以必须是中位数。 对于带权中位数。对于每