在 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}

**解释** -

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

解决方案方法

解决这个问题的一个简单方法是遍历所有查询，对所有查询使用我们解决它的方法来解决它们，然后最后返回找到的数组。在这里，为了找到 initialArray，我们需要以相反的方式操作它，即从给定数组中减去它。

示例

程序演示了我们解决方案的工作原理

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

输出

Initial array : 7 0 7 -1 6

sudhir sharma

更新于：2022年1月28日

209 次浏览

开启你的职业生涯

完成课程获得认证

开始学习