Rechercher le tableau initial d'un tableau donné après une requête de somme de plage en C++

Dans ce problème, nous obtenons un tableau res[] de taille N. Notre tâche est de trouver le tableau initial à partir d'un tableau donné après une requête de somme de plage.

Nous devons trouver le tableau de départ sur lequel le tableau rel[] sera renvoyé lors de l'exécution d'une requête [s, e, val].

Chaque requête [s, e, val] est résolue comme

s -> index de début

e -> index de fin

val -> mettre à jour chaque élément de s à e pour être ajouté à la valeur du tableau.

Prenons un exemple pour comprendre ce problème, la traduction de

Input : rel[] = {7, 4, 8}
Query[][] = {{1, 2, 1},
{0, 1, 3}}
Output : {4, 0, 7}

Explication −

est :

Explication −

initialArray = {4, 0, 7}; query = {1, 2, 1}; finalArray = {4, 1, 8}
initialArray = {4, 1, 8}; query = {0, 1, 3}; finalArray = {7, 4, 8}

Solution

La façon simple de résoudre le problème est de parcourir tout requêtes, pour tous La requête est résolue de la même manière que nous avons résolu le problème, puis renvoie le tableau trouvé à la fin. Ici, afin de trouver le tableau initial, nous devons l'opérer de la manière opposée, c'est-à-dire le soustraire du tableau donné.

Exemple

Exemple de programme pour illustrer le fonctionnement de notre solution

#include <iostream>
using namespace std;
void calcInitialArrayQueries(int arr[], int n, int query[][3], int q) {
   for (int i = 0; i < q; i++) {
      for (int j = query[i][0];j <= query[i][1]; j++) {
         arr[j] = arr[j] - query[i][2];
      }
   }
   for (int i = 0; i < n; i++)
      cout<<arr[i]<<" ";
}
int main() {
   int arr[] = { 5, 1, 8, 2, 9};
   int n = sizeof(arr) / sizeof(arr[0]);
   int query[][3] = { {0, 2, -2}, {1, 4, 3}};
   int q = sizeof(query) / sizeof(query[0]);
   cout<<"Initial array : "; calcInitialArrayQueries(arr, n, query, q);
   return 0;
}

Sortie

Initial array : 7 0 7 -1 6

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!