arrays - 配列を等化するために必要な変換の最小数

Question

n個の正の要素（0を含む）の配列が与えられます。リストの各要素を1つを除いてインクリメントする変換を1つだけ実行できます。このリストを均等化するために必要な変換の最小数はいくつですか？

たとえば、、n = 3および配列は1,2,3。次のような3つの変換が必要です。

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

必要な変換の最小数であるリストは6ですn = 4。1,3,2,4

これを解決するための最良のアプローチはどれですか？

Answer 1

実際に変換を表示する必要はありませんが、必要なそのような変換の総数を見つける必要があります。

1つの要素を除くすべてをインクリメントすることは、基本的に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つの要素から1を引くことと同じであり、最後のステップとして各要素にnを追加することと同じであることに気付いた場合、これについて議論するのははるかに簡単です。ここで、nは変換の数です。例：1,2,3-> 1,2,2-> 1,1,2->1,1,1そして最後に4,4,4

そしてもちろん、これは、sum_i（a_i --m）変換が必要であることを意味します（配列の場合、a_iはi番目の要素、mは配列の最小要素です）。

だからあなたのアプローチは

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