En C++, trouvez le nombre d'opérations nécessaires pour rendre tous les éléments d'un tableau égaux

Dans ce problème, nous obtenons un tableau arr de taille n. Notre tâche est de trouver le nombre d'opérations nécessaires pour rendre tous les éléments du tableau égaux

L'opération est définie comme distribuer les éléments du tableau de l'élément ayant le plus grand poids à un poids égal de tous les éléments.

S'il n'est pas possible de rendre les éléments du tableau égaux, imprimez -1.

Prenons un exemple pour comprendre ce problème,

Input : arr[] = {7, 3, 3, 3}
Output : 3

Explication

Le tableau alloué est {4, 4, 4, 4}

Solution

Un moyen simple de résoudre ce problème est de trouver Le valeur maximale du tableau. Cette valeur maximale est ensuite utilisée pour vérifier si tous les éléments du tableau sont égaux et si la valeur est égale à la valeur maximale du tableau moins n (ou un multiple de celle-ci). Si oui, n est renvoyé, si non, -1 est renvoyé (indiquant que ce n'est pas possible).

Exemple

Prenons un exemple pour comprendre le problème

#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;
}

Sortie

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!