C++에서 범위 합계 쿼리 후 주어진 배열에서 초기 배열 찾기

이 문제에서는 크기가 N인 배열 res[]를 얻습니다. 우리의 임무는 범위 합계 쿼리 후 주어진 배열에서 초기 배열을 찾는 것입니다.

[s, e, val] 쿼리를 실행할 때 배열 rel[]이 반환될 시작 배열을 찾아야 합니다.

각 [s, e, val] 쿼리는

s -> 시작 인덱스

e -> 끝 인덱스

val -> 각 요소를 s에서 e로 업데이트하여 배열 값에 추가하는 방식으로 해결됩니다.

이 문제를 이해하기 위해 예를 들어 보겠습니다.

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

Explanation −

을 번역하면 다음과 같습니다.

Explanation −

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

문제를 해결하는 간단한 방법은 전체를 반복하는 것입니다. 쿼리, for all 쿼리는 문제를 해결한 것과 동일한 방식으로 해결된 다음 마지막에 찾은 배열을 반환합니다. 여기서 초기 배열을 찾으려면 반대 방식으로 이를 연산해야 합니다. 즉, 주어진 배열에서 이를 빼야 합니다.

예

우리 솔루션의 작동 방식을 보여주는 프로그램 예제

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

Output

Initial array : 7 0 7 -1 6

위 내용은 C++에서 범위 합계 쿼리 후 주어진 배열에서 초기 배열 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!