arrays - 均衡数组所需的最少变换次数

Question

给定一个包含 n 个正元素（包括 0）的数组。我们只允许执行一种转换，即增加列表中除一个之外的每个元素。均衡此列表所需的最少转换次数是多少？

例如n = 3， 和数组是1,2,3。我们需要 3 个这样的转换：

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

n = 4并且列表是所需的1,3,2,4最小转换次数是 6

解决这个问题的最佳方法是什么？

Answer 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

Answer 2

如果您意识到您的转换与从一个元素中减去 1 相同，并且作为最后一步将 n 添加到每个元素，其中 n 是转换的数量，那么争论这一点会容易得多。例如 1,2,3->1,2,2->1,1,2->1,1,1 最后是 4,4,4

这当然意味着您需要（使用 a 数组，a_i 第 i 个元素，m 数组中的最小元素） sum_i(a_i - m) 转换。

所以你的方法是

m=min(a)
for each (e in a) {
   while (e>m) {
      //transform so that e is reduced by 1
   }
}