我们得到一个包含整数的数组 Arr[] 和包含查询的二维数组 Q。每个查询包含 3 个值，分别是 lpos、rpos 和 K。一个可以在一个步骤中从索引 i 移动到下一个索引 i+1 或保留在该索引中。最多只能以 K 步从 lpos 移动到 rpos。在每一步添加所有数字，包括最左边的数字。目标是在最大 K 次移动中最大化总和。如果在 K 步中不可能从 lpos 移动到 rpos，则打印“No”。让我们了解更多。
让我们看看这个的各种输入输出场景 -
在 - Arr[] = {1, 2, 4, -1 };
Q[][3] = { { 0, 2, 2 }, { 0, 2, 1 }, { 3, 3, 1 }, { 0, 2, 3} };
出 -
查询 1：7
查询 2：否
查询 3：否
查询 4：11
说明 -
我们可以在最多 2 个步骤中从索引 0 移动到 2：-
步骤 1:- 索引 0 到 1 ( 1+2=3 )
第 2 步：- 索引 1 到 2 ( 3+4=7 )
我们不能在最大 1 步中从索引 0 移动到 2。打印“否”
我们不能在最大 1 步中从索引 3 移动到 3。打印“否”
我们可以在最多 3 个步骤中从索引 0 移动到 2：-
步骤 1:- 索引 0 到 1 ( 1+2=3 )
第 2 步：- 索引 1 到 2 ( 3+4=7 )
第 3 步：- 保持索引 2 ( 7+4=11 )
在 - Arr[] = { 1, 2, 3, 3, 2 }; Q[][3] = { { 0, 3, 2 }, { 1, 4, 3 } };
出 -
查询 1：否
查询 2：10
说明 -
我们不能在最大 1 步中从索引 0 移动到 2。打印“否”
我们可以最多分 3 个步骤从索引 1 移动到 4：-
第 1 步：- 索引 1 到 2 ( 2+3=5 )
第 2 步：- 索引 2 到 3 ( 5+3=8 )
第 3 步：- 索引 3 到 4 ( 8+2=10 )
在这种方法中，我们将使用 lpos 到 rpos 范围的段树来找到可能的最大值并使用前缀和计算所有数字的总和。
取输入数组 Arr[] 和查询矩阵 Q[][]。
以 sgTreee[5 * length] 为数组实现段树。
取 pSum[length] 作为前缀和数组。
函数 createTree(int min, int max, int pos, int sgT[], int arr[], int len) 用于在段树中创建值。
检查是否 (min == max) 这意味着它是一个叶节点。设置 sgT[pos] = arr[max]。
取 midd = (min + max) / 2。
为左右子树调用 createTree(min, midd, loc1, sgT, arr, len) 和 createTree(midd + 1, max, loc2, sgT, arr, len) 以获取左右子树，其中 loc1=2*pos+1 和 loc2=2*位置+2。
取 tmp1=sgT[loc1] 和 tmp2=sgT[loc2] 并用 tmp1 或 tmp2 中的最大值更新 sgT[pos]。
函数 preSum(int pSum4[], int arr4[], int len4) 获取输入数组并使用 for 循环更新前缀数组。
对于从索引 1 到最后一个的每个元素，更新 pSum4[j] = pSum4[j - 1] + arr4[j];
函数 resQuery(int len3, int arr3[], int sgT3[], int pSum3[], int q1[][3], int qlen1) 接受所有输入参数并打印每个查询的结果。
在里面resQuery()，调用solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]) 使用for循环对每个查询一一求解。
函数 solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]) 求解查询并返回结果。
如果 rpos - lpos > k 则返回 -1，因为不可能有解决方案。
取 maxVal = findMax(0, len2 - 1, lpos, rpos, 0, sgT2, arr2, len2);
如果 maxVal < 0，则将 maxVal 设置为 0
取变量 sum = pSum2[rpos]。
如果 lpos > 0 则设置 sum -= pSum2[lpos - 1] 并且 result = sum + (k - (rpos - lpos)) * maxVal。
返回结果。
函数 findMax(int start, int end, int min1, int max1, int pos1, int sgT1[], int arr1[], int len1) 返回范围 lpos 和 rpos 之间的最大值。
如果 (min1 <= start) 和 (max1 >= end) 则返回 sgT1[pos1] 因为存在重叠。
如果 (end < min1 || start > max1) 则发生超出范围，因此返回 INT_MIN。
使用递归调用左子树和右子树计算 lmax 和 rmax 并返回两个最大值。
最后，将为每个查询打印结果。如果没有解决方案，则为“否”
#include <bits/stdc++.h>
using namespace std;
void createTree(int min, int max, int pos,
int sgT[], int arr[], int len){ if (min == max) {
sgT[pos] = arr[max];
return;
}
int midd = (min + max) / 2;
int loc1=2*pos+1;
int loc2=2*pos+2;
createTree(min, midd, loc1, sgT, arr, len);
createTree(midd + 1, max, loc2, sgT, arr, len);
int tmp1=sgT[loc1];
int tmp2=sgT[loc2];
sgT[pos] = tmp1>tmp2 ? tmp1 : tmp2 ;
}
int findMax(int start, int end, int min1, int max1, int pos1, int sgT1[], int arr1[], int len1){
int middle;
if (min1 <= start)
{ if( max1 >= end){
return sgT1[pos1];
}
}
if (end < min1 || start > max1)
{ return INT_MIN; }
middle = (start + end) / 2;
int loc1=2 * pos1 + 1;
int loc2=2 * pos1 + 2;
int lmax = findMax(start, middle, min1, max1, loc1, sgT1, arr1, len1);
int rmax = findMax(middle + 1, end, min1, max1, loc2, sgT1, arr1, len1);
int res=lmax>rmax?lmax:rmax;
return res;
}
int solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]){
int result;
if (rpos - lpos > k)
{ return -1; }
int maxVal = findMax(0, len2 - 1, lpos, rpos, 0, sgT2, arr2, len2);
if (maxVal < 0)
{ maxVal = 0; }
int sum = pSum2[rpos];
if (lpos > 0)
{ sum -= pSum2[lpos - 1]; }
result = sum + (k - (rpos - lpos)) * maxVal;
return result;
}
void resQuery(int len3, int arr3[], int sgT3[],
int pSum3[], int q1[][3], int qlen1){
int i;
int result;
for (i = 0; i < qlen1; i++) {
result = solQuery(q1[i][0], q1[i][1],q1[i][2], len3, arr3, sgT3, pSum3);
if (result == -1)
{ cout <<endl<<"Query "<<i+1<<": "<<"NO"; }
else
{ cout <<endl<<"Query "<<i+1<<": "<<result; }
}
}
void preSum(int pSum4[], int arr4[], int len4){
pSum4[0] = arr4[0];
int j;
for (j = 1; j < len4; j++){
pSum4[j] = pSum4[j - 1] + arr4[j];
}
}
int main(){
int Arr[] = {1, 2, 4, -1 };
int length = sizeof(Arr) / sizeof(Arr[0]);
int sgTreee[5 * length];
createTree(0, length - 1, 0, sgTreee, Arr, length);
int pSum[length];
preSum(pSum, Arr, length);
int Q[][3] = { { 0, 2, 2 },
{ 0, 2, 1 },
{ 3, 3, 1 },
{ 0, 2, 3} };
int qlen = sizeof(Q) / sizeof(Q[0]);
resQuery(length, Arr, sgTreee, pSum, Q, qlen);
return 0;
}输出结果如果我们运行上面的代码，它将生成以下输出
Query 1: 7 Query 2: NO Query 3: NO Query 4: 11