中位数这个东西他他他他他……
我********
步入正题
题意
给定一个长度为 \(n\) 的数列 \(\{a_n\}\)，现要求删除 \(k\) 个数后求一个使
\[\sum_{i=1}^n|a_i-a_x|
\]
最小的位置 \(x\)。
首先明确一个事，就是当 \(a_x\) 为中位数的时候差之和最小，中位数是什么就不用我说了吧所以这个题目怎么做就很明确了：
- 当 \(n\) 为奇数时，\(x\) 取 \(\frac{1}{2}(n+1)\)；
- 当 \(n\) 为偶数时，\(x\) 取 \(\frac{1}{2}n+1\)。
然后再按照题目模拟即可，记得要排序。
代码我就不放了。