数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在C++中，在最多K步内，在[L, R]范围内最大化数字的总和
给定一个包含整数的数组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：NO
查询 3：NO
查询 4：11
解释 -
第一个查询：
我们可以在最多2步内从索引0移动到2：
步骤 1：索引 0 到 1 ( 1+2=3 )
步骤 2：索引 1 到 2 ( 3+4=7 )
第二个查询：
我们无法在最多1步内从索引0移动到2。打印“NO”
第三个查询：
我们无法在最多1步内从索引3移动到3。打印“NO”
第四个查询：
我们可以在最多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：NO
查询 2：10
解释 -
第一个查询：
我们无法在最多1步内从索引0移动到2。打印“NO”
第二个查询：
我们可以在最多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*pos+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()内部，使用for循环逐个调用solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[])来解决每个查询。
函数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。
返回result。
函数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，并返回两者的最大值。
最后，将为每个查询打印结果。“No”表示没有解决方案
示例
#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
99 次浏览
