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
Le tableau alloué est {4, 4, 4, 4}
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).
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; }
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!