给定n个正元素(包括0)的数组。我们只允许执行一种转换,即增加列表中除一个元素之外的每个元素。要使此列表均等,最少需要多少次转换?
例如,n = 3和数组为1,2,3。我们需要3这样的转换:
n = 3
1,2,3
2,3,3 --> 3,3,4 --> 4,4,4。
2,3,3 --> 3,3,4 --> 4,4,4
对于n = 4,并且列表是1,3,2,4所需的最少转换数量为6
n = 4
1,3,2,4
哪个是解决此问题的最佳方法?
您实际上不需要显示转换,但可以找到所需的转换总数。
增加一个元素以外的所有元素与减少一个元素本质上是相同的(出于均衡所有元素的目的)。
策略 :减少所有非最小元素,直到它们等于最小元素。
例如 如果元素是{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