資料結構
網路
關係資料庫管理系統 (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 次瀏覽
