Réorganiser un tableau pour maximiser i*arr, en utilisant C++

Dans cet article, nous aborderons le problème de la réorganisation d'un tableau donné de n nombres. Fondamentalement, nous devons sélectionner des éléments dans un tableau. Pour sélectionner chaque élément, on obtient quelques points qui seront évalués par la valeur de l'élément courant * le nombre d'éléments sélectionnés avant l'élément courant. Vous devez sélectionner des éléments pour obtenir le score le plus élevé. Par exemple -

Input : arr[ ] = { 3, 1, 5, 6, 3 }

If we select the elements in the way it is given, our points will be
   = 3 * 0 + 1 * 1 + 5 * 2 + 6 * 3 + 3 * 4
   = 41
To maximize the points we have to select the elements in order { 1, 3, 3, 5, 6 }
   = 1 * 0 + 3 * 1 + 3 * 2 + 5 * 3 + 6 * 4
   = 48(maximum)

Output : 48

Input : arr[ ] = { 2, 4, 7, 1, 8 }
Output : 63

Méthodes pour trouver des solutions

En regardant cet exemple, nous devons obtenir le point maximum, nous devons sélectionner les éléments du petit au grand. La solution est trouvée en triant

• le tableau donné par ordre croissant.
• Commencez à sélectionner les éléments de l'index 0 jusqu'à la fin.
• Calculez le score obtenu en sélectionnant chaque élément.

Exemple

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

int main () {
   int arr[] = { 2, 4, 7, 1, 8 };
   int n = sizeof (arr) / sizeof (arr[0]);
   // sorting the array
   sort (arr, arr + n);

   int points = 0;
   // traverse the array and calculate the points
   for (int i = 0; i < n; i++) {
      points += arr[i] * i;
   }
   cout << "Maximum points: " << points;
   return 0;
}

Sortie

Maximum points: 63

La description du code ci-dessus

Ce code C++ est facile à comprendre. Nous trions d’abord le tableau, puis utilisons une boucle for pour parcourir le tableau et calculer le score obtenu en sélectionnant chaque élément du début à la fin.

Conclusion

Dans cet article, nous avons discuté du problème de la sélection d'éléments dans un tableau pour obtenir le point maximum, où le point est calculé par i * arr[i]. Nous adoptons une approche gourmande pour résoudre ce problème et obtenir le score maximum. Discutant également du code C++ pour faire de même, nous pouvons écrire ce code dans n'importe quel autre langage comme C, Java, Python, etc. J'espère que cet article vous sera utile.

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!