C++で配列要素の移動だけで配列を均等化するために必要な操作回数を求める方法

この記事では、n個の要素を持つ配列が与えられたとき、配列内の要素同士で値を受け渡すことによってすべての要素を同じ値に揃える（均等化する）ために必要な操作回数を求めるC++プログラムを紹介します。

ここでいう「1回の操作」とは、ある要素から値を1だけ引き、その分を別の要素へ1だけ加えることを指します。つまり減算と加算を合わせて1セットとしてカウントします。重要なのは、値の受け渡しによって配列全体の合計は常に変わらないという点です。

問題例

入力： arr[] = {4, 0, 3, 1, 2}

出力： 3

説明：

最終的にすべての要素が揃う値は「2」です。

• arr[0] の値 4 から 2 を取り出し、arr[1] の値 0 に加える → 配列は {2, 2, 3, 1, 2} になります
• arr[2] の値 3 から 1 を取り出し、arr[3] の値 1 に加える → 配列は {2, 2, 2, 2, 2} になります

以上より、必要な操作回数は 3 回となります。

解法のアプローチ

まず、そもそも配列を均等化できるかどうかを判定します。その鍵となるのが平均値です。配列全体の合計を要素数で割った値が整数でない場合、すべての要素を同一の整数値にすることはできないため、均等化は不可能です。

均等化が可能な場合は、各要素と平均値との差の絶対値をすべて合計します。1回の操作を行うたびに、「値を渡す側」と「値を受け取る側」の両方で平均との差が1ずつ縮まる、つまり絶対差の合計が2ずつ減少するため、必要な操作回数は絶対差の合計の半分になります。

アルゴリズム

1. ステップ1： 配列の全要素の合計を求め、平均値を計算します。
2. ステップ2： 合計が要素数で割り切れない場合は -1 を返し、均等化が不可能であることを示します。
3. ステップ3： 可能な場合は、各要素と平均値の絶対差を合計します。
4. ステップ4： 絶対差の合計を2で割った値（＝操作回数）を返します。

C++による実装例

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

int calcEqualisedOperations(int arr[], int n) {
    int sum = 0, operations = 0;

    // 全要素の合計を求める
    for (int i = 0; i < n; i++)
        sum += arr[i];

    // 合計が要素数で割り切れない場合、均等化は不可能
    if (sum % n != 0)
        return -1;

    int average = sum / n;

    // 各要素と平均値の絶対差を合計する
    for (int i = 0; i < n; i++)
        operations += abs(arr[i] - average);

    // 操作回数は絶対差の合計の半分
    return operations / 2;
}

int main() {
    int arr[] = { 4, 0, 3, 1, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "配列を均等化するために必要な操作回数は "
         << calcEqualisedOperations(arr, n)
         << " 回です" << endl;

    return 0;
}

出力

配列を均等化するために必要な操作回数は 3 回です

計算量の評価

時間計算量： O(n) ― 配列を合計の計算と絶対差の集計のために2回走査するだけです。
空間計算量： O(1) ― 集計用の変数以外に追加の記憶域は不要です。

まとめ

配列の均等化問題は、「合計が保存される」という性質と「平均値」に着目することで効率的に解けます。平均値が整数かどうかの判定で実行可能性を確認し、絶対差の合計の半分を取るだけで最小操作回数が求まります。負の値が含まれる配列でも、abs() を使った絶対差の計算により正しく動作します。