转型的最低数量要求，以平衡阵列 [英] Minimum number of transformation required to equalize an array

问题描述

由于正积极元素（包括0）阵列。我们允许执行其递增列表的每个元素除了一个只有一个转化。什么是转型的均衡这个列表中选择所需的最低数量？

Given an array of n positive elements (including 0). We are allowed to perform only one transformation which is to increment each element of the list except one. What are the minimum number of transformation required to equalize this list?

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

For example, n = 3, and the array being 1,2,3. We need 3 such transformation as:

2,3,3 - ＆GT; 3,3,4 - ＆GT; 4,4,4 。

有关 N = 4 和列表是 1,3,2,4 转型的最低数量要求6

For n = 4 and the list being 1,3,2,4 the minimum number of transformation required is 6

这是解决这一问题的最佳方法？

Which is the best approach to solve this?

推荐答案

您实际上并不需要显示的转换，却发现需要这种转换的总数量。

You do not actually need to show the transformations but find the total number of such transformations required.

递增所有而不是一个元件基本上相同降低一个元件（用于均衡所有元素的目的）。

Incrementing all but one element is essentially the same as decreasing one element(for the purpose of equalizing all elements).

策略：  降低所有非最小的元素，直到他们平等的最小元素。

strategy: decrease all non-minimal elements until they equal the minimal element.

有关，例如。如果元素是{X1，X2，X3，X4 ...... XN} 变换的数量将是

for eg. If the elements are {x1, x2, x3, x4...... xn} the number of transformations will be

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

这篇关于转型的最低数量要求，以平衡阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！