均衡数组所需的最小转换次数[关闭]

Question

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

例如，< code>n = 3，数组为< code>1，2，3。我们需要3个这样的转换:

2,3,3--

对于< code>n = 4并且列表为< code>1，3，2，4，所需的最小变换数是6

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

Answer 1

如果你意识到你的变换与从一个元素中减去1是一样的，最后一步是将n加到每个元素上，其中n是变换的次数，那么争论起来就容易多了。e、 g 1,2,3-

这当然意味着需要（对于数组，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
   }
} 

Answer 2

您实际上不需要显示转换，而是找到所需的此类转换的总数。

增加除一个元素之外的所有元素本质上与减少一个元素相同（为了均衡所有元素）。

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

例如，如果元素是{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