C++で配列のすべての要素を等しくするために必要な操作回数を求める方法

この問題では、サイズ n の配列 arr が与えられます。私たちのタスクは、配列のすべての要素を等しくするために必要な操作回数を求めることです。

ここでいう「操作」とは、最大の重みを持つ要素から、配列内の他のすべての要素へ等しい重みを分配することを意味します。

すべての要素を等しくすることが不可能な場合は、-1 を出力します。

それでは、具体例を使って問題を確認してみましょう。

入力 : arr[] = {7, 3, 3, 3}
出力 : 3

解説

分配操作を行った結果、配列は {4, 4, 4, 4} となり、すべての要素が等しい値に揃います。最大値 7 を持つ要素から他の要素へ重みを分配する操作を合計 3 回繰り返すことで、この状態に到達できます。

解法のアプローチ

この問題に対する基本的な解法は、まず配列内の最大値を求めるところから始まります。次に、その最大値を基準として、すべての要素を等しくできるかどうかを判断します。具体的には、各要素の値が「最大値から n（またはその倍数）を差し引いた値」と一致するかを確認します。条件を満たす場合は必要な操作回数を返し、満たさない場合は -1（等しくすることが不可能であることを示す値）を返します。

実装例

それでは、このアプローチを C++ で実装してみましょう。

#include<bits/stdc++.h>
using namespace std;
int findOperationCount(int arr[],int n){
    int j = 0, operations = 0;
    int maxVal = arr[0];
    int minVal = arr[0];
    int maxValInd = 0;
    for (int i = 1; i < n; i++){
        if(arr[i] > maxVal){
            maxVal = arr[i];
            maxValInd = i;
        }
        if(arr[i] < minVal){
            minVal = arr[i];
        }
    }
    for (int i =0;i<n;i++){
        if (arr[i] != maxVal && arr[i] <= minVal && arr[i] != 0){
            arr[j] += 1;
            arr[maxValInd] -= 1;
            maxVal -= 1;
            operations += 1;
            j += 1;
        }
        else if (arr[i] != 0){
            j += 1;
        }
    }
    for (int i = 0; i < n; i++){
        if (arr[i] != maxVal){
            operations = -1;
            break;
        }
    }
    return operations;
}
int main(){
    int arr[] = {4, 4, 8, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"The number of operations required to make all array  elements Equal is "<<findOperationCount(arr, n);
    return 0;
}

出力

The number of operations required to make all array elements Equal is 3

このように、プログラムは配列 {4, 4, 8, 4} に対して、すべての要素を等しくするために必要な操作回数として 3 を出力します。