정수를 포함하는 배열 Arr[]과 쿼리를 포함하는 2D 배열 Q가 제공됩니다. 각 쿼리에는 lpos, rpos 및 K인 3개의 값이 포함됩니다. 하나는 단일 단계에서 인덱스 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[][]를 쿼리합니다.
-
세그먼트 트리를 구현하기 위한 배열로 sgTree[5 * length]를 사용합니다.
-
pSum[length]을 접두사 합계 배열로 사용합니다.
-
함수 createTree(int min, int max, int pos, int sgT[], int arr[], int len)는 세그먼트 트리에서 값을 생성하는 데 사용됩니다.
-
(최소 ==최대) 리프 노드인지 확인하십시오. sgT[pos] =arr[max]로 설정합니다.
-
중간 =(최소 + 최대) / 2.
-
loc1=2*pos+1 및 loc2=2*인 왼쪽 및 오른쪽 하위 트리에 대해 createTree(min, midd, loc1, sgT, arr, len) 및 createTree(midd + 1, max, loc2, sgT, arr, len)를 호출합니다. 위치+2.
-
tmp1=sgT[loc1] 및 tmp2=sgT[loc2]를 사용하고 sgT[pos]를 tmp1 또는 tmp2 중 최대값으로 업데이트합니다.
-
함수 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으로 설정
-
변수 합계 =pSum2[rpos]를 사용합니다.
-
lpos> 0이면 sum -=pSum2[lpos - 1]로 설정하고 결과 =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
max1)이면 범위 밖이 발생하므로 INT_MIN을 반환합니다. -
왼쪽 및 오른쪽 하위 트리에 대한 재귀 호출을 사용하여 lmax 및 rmax를 계산하고 최대 2개를 반환합니다.
-
마지막에 결과가 각 쿼리에 대해 인쇄됩니다. 해결책이 없는 경우 "아니오"
예
#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