タワーで達成できる最小限の醜さを見つけるためのC++プログラム

n個の要素を持つ配列Aがあるとします。 n個のブロックタワーが連続していると考えてください。 i番目のタワーの高さはA[i]です。 1日で、次の操作を実行できます。2つのインデックスiとj（i！=j）を選択し、タワーiからjに戻ります。 A [i]が1減少し、A [j]が1増加します。建物の醜さはmax（A）− min（A）です。達成できる最小限の醜さを見つける必要があります。

したがって、入力がA =[1、2、3、1、5]の場合、出力は1になります。これは、i=2とj=0に対して3つの操作を実行できるため、新しい配列は[ 2,2,2,1,5]の場合、i=4およびj=3の場合、配列は[2,2,2,2,4]になり、i=4およびj=2の場合、配列は[ 2,2,3,2,3]。

ステップ

これを解決するには、次の手順に従います-

sum := 0
x := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   sum := sum + A[i]
if sum mod n is same as 0, then:
   return 0
return 1

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
   int sum = 0, x = 0;
   int n = A.size();
   for (int i = 0; i < n; i++)
      sum += A[i];
   if (sum % n == 0)
      return 0;
   return 1;
}
int main() {
   vector<int> A = { 1, 2, 3, 1, 5 };
   cout << solve(A) << endl;
}

入力

{ 1, 2, 3, 1, 5 }

出力

1