Finden Sie das anfängliche Array aus einem bestimmten Array nach der Bereichssummenabfrage in C++

In diesem Problem erhalten wir ein Array res[] der Größe N. Unsere Aufgabe besteht darin, nach der Bereichssummenabfrage das erste Array aus einem gegebenen Array zu finden.

Wir müssen das Startarray finden, auf dem das Array rel[] zurückgegeben wird, wenn eine [s, e, val]-Abfrage ausgeführt wird.

Jede [s, e, val]-Abfrage wird gelöst als

s -> Startindex

e -> Endindex

val -> jedes Element von s auf e aktualisieren, um es dem Array-Wert hinzuzufügen.

Nehmen wir ein Beispiel, um dieses Problem zu verstehen. Die Übersetzung von

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

Erklärung −

lautet:

Erläuterung −

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

Lösung

Der einfache Weg, das Problem zu lösen, besteht darin, alles zu durchlaufen Abfragen für alle Die Abfrage wird auf die gleiche Weise gelöst, wie wir das Problem gelöst haben, und am Ende wird das gefundene Array zurückgegeben. Um das anfängliche Array zu finden, müssen wir es hier umgekehrt verarbeiten, d. h. es vom gegebenen Array subtrahieren.

Beispiel

Programmbeispiel zur Veranschaulichung der Funktionsweise unserer Lösung

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

Ausgabe

Initial array : 7 0 7 -1 6

Das obige ist der detaillierte Inhalt vonFinden Sie das anfängliche Array aus einem bestimmten Array nach der Bereichssummenabfrage in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!