讨论/算法和数据结构/关于正整数数组绝对值收敛到指定区间N的问题,求最优算法/
关于正整数数组绝对值收敛到指定区间N的问题,求最优算法

数组绝对值收敛问题

求最优算法,一个正整数数组,要使得任意俩个元素差绝对值不大于N的话,最小代价是多少。
例如 [1,3,4,5,8], N = 3,将1改为3, 8改为6,则最小修改的代价是4;
限定条件:
1 <= 元素以及个数 <= 10^5
1 <= N <= 10^5

共 1 个回复

维护一个关于数字 1 - 10^5 的数组,数组里记录数字出现的次数
然后可以用一个滑动窗口枚举[允许最小值,允许最大值]的位置
比如示例 [1,3,4,5,8]
转换为数组 [1,0,1,1,1,0,0,1]
然后当滑动窗口到 [1,0,[1,1,1,0],0,1]时代价为4.
复杂度 O(M), M = 允许出现的最大数字