Skip to content

14277: 【原4277】小可怜的中位数

题目

题目描述

author: 小可怜 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4277

小可怜的中位数

Description

助教是个小可怜,因为她不知道要出什么机考题了。 然后她发现大家的小作业里面似乎有贪心题,所以就提出了这样一个问题: 小可怜助教读入了一列数(保证这列数有奇数个数),她想通过修改这列数,把它们的中位数变为$mid$,那么每个数字数值上的变化的绝对值之和的最小值究竟是多少呢? 这似乎是件很好玩的事情,所以小可怜助教就把这个问题出成了这道机考题┓( ´∀` )┏。

Input Format

第一行两个整数$n,mid$表示这列数有$n$个,中位数需要被修改为$mid$\ 之后一行$n$个整数,表示这列数。

Output Format

一个整数,表示小可怜助教想要的结果。

SAMPLE INPUT

3 9
6 7 9

SAMPLE OUTPUT

2

SAMPLE EXPLANATION

现有的数列为 6 7 9,只用把 7 变为 9,数列变为6 9 9,此时中位数就为 9,此时,每个数字数值上的变化的绝对值之和为$|6-6|+|7-9|+|9-9|=2$, 为可以达到的最小值。

DATA LIMIT

40%的数据满足 $1 < n < 10$ 且保证$n$为奇数. 100%的数据满足 $1 < n < 1000$ 且保证$n$为奇数. 数列中的数 $a_i$ 保证有 $0 \leq a_i,mid \leq 10^9$.

Hint

小可怜助教很可怜但还是给了大家一些关于贪心算法的提示。 贪心是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。 这道题目中可以尝试考虑大小在现有的中位数和$mid$之间的数字。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!