Programme C++ : Calculer le nombre d'opérations nécessaires pour placer un élément avec un index inférieur à une valeur

Supposons que nous ayons un tableau A contenant n éléments. Nous pouvons effectuer ces opérations plusieurs fois -

• sélectionnez n'importe quel entier positif k

• sélectionnez n'importe quelle position et insérez k à cette position

• De cette façon, la séquence change et nous continuons cette séquence dans l'opération suivante.

ul>

Nous devons trouver le nombre minimum d'opérandes requis pour satisfaire la condition : A[i]

Donc, si l'entrée est, disons A = [1, 2, 5, 7, 4] alors la sortie sera 3 car nous pouvons faire quelque chose comme : [1,2,5,7,4] à [1, 2 ,3,5,7,4] à [1,2,3,4,5,7,4] à [1,2,3,4,5,3,7,4].

Étapes h2>

Pour résoudre ce problème, nous suivrons les étapes suivantes -

maxj := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   maxj := maximum of maxj and (A[i] - i - 1)
return maxj

Exemple

Voyons l'implémentation suivante pour une meilleure compréhension −

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

int solve(vector<int> A) {
   int maxj = 0;
   int n = A.size();
   for (int i = 0; i < n; i++) {
      maxj = max(maxj, A[i] - i - 1);
   }
   return maxj;
}
int main() {
   vector<int> A = { 1, 2, 5, 7, 4 };
   cout << solve(A) << endl;
}

Input

{ 1, 2, 5, 7, 4 }

Output

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!