shencode 2022-04-07 14:47:49 2022-04-07 14:49:29 14 返回题目
由题意知要使原整数序列 变为连续序列、、、的最小修改量,即求:的最小值
稍作变换:,将更新为,则转化为求:的最小值。
实际上,可将其视为在一条数轴上(对升序排序),找一个整数点使得到其距离和最小,该点可用的中位数即可。
时间复杂度为O(nlgn)。