小编典典

均衡数组所需的最小变换数

algorithm

给定n个正元素(包括0)的数组。我们只允许执行一种转换,即增加列表中除一个元素之外的每个元素。要使此列表均等,最少需要多少次转换?

例如,n = 3和数组为1,2,3。我们需要3这样的转换:

2,3,3 --> 3,3,4 --> 4,4,4

对于n = 4,并且列表是1,3,2,4所需的最少转换数量为6

哪个是解决此问题的最佳方法?


阅读 297

收藏
2020-07-28

共1个答案

小编典典

您实际上不需要显示转​​换,但可以找到所需的转换总数。

增加一个元素以外的所有元素与减少一个元素本质上是相同的(出于均衡所有元素的目的)。

策略 :减少所有非最小元素,直到它们等于最小元素。

例如 如果元素是{x1,x2,x3,x4 … xn},则转换次数为

let min = min{x1 .. xn}
for(int x : arr){
    // decrement x until x == m
}

转换总数

sum(k = 1 to n)x(k)−n*min{x1,…,xn}

样品运行:

For array = {1,2,3}
sum(k=1 to n) x(k) = (1 + 2 + 3) = 6
n = 3
min = 1
num_transformations = 6 - 3*1 = 3 transformations
2020-07-28