Chúng ta được cung cấp một mảng Arr [] chứa các số nguyên và mảng 2D Q chứa các truy vấn. Mỗi truy vấn chứa 3 giá trị là lpos, rpos và K. Người ta có thể di chuyển từ chỉ mục i sang chỉ mục tiếp theo i + 1 trong một bước duy nhất hoặc giữ nguyên trong chỉ mục đó. Một người có thể chuyển từ lpos sang rpos chỉ trong tối đa K bước. Thêm tất cả các số ở mỗi bước bao gồm cả số ngoài cùng bên trái. Mục đích là để tối đa hóa tổng trong K nước đi tối đa. Nếu không thể di chuyển từ lpos sang rpos trong K bước thì hãy in “Không”. Hãy để chúng tôi hiểu thêm.
Hãy cho chúng tôi xem các tình huống đầu ra đầu vào khác nhau cho việc này -
Trong - Arr [] ={1, 2, 4, -1};
Q [] [3] ={{0, 2, 2}, {0, 2, 1}, {3, 3, 1}, {0, 2, 3}};
Hết -
Truy vấn 1:7
Truy vấn 2:KHÔNG
Truy vấn 3:KHÔNG
Truy vấn 4:11
Giải thích -
Truy vấn đầu tiên:-
Chúng ta có thể chuyển từ chỉ mục 0 sang chỉ số 2 trong 2 bước tối đa:-
Bước 1:- chỉ mục 0 đến 1 (1 + 2 =3)
Bước 2:- chỉ mục 1 đến 2 (3 + 4 =7)
Truy vấn thứ hai:-
Chúng ta không thể chuyển từ chỉ số 0 sang chỉ số 2 trong 1 bước tối đa. In “KHÔNG”
Truy vấn thứ ba:-
Chúng ta không thể chuyển từ chỉ số 3 sang chỉ số 3 trong 1 bước tối đa. In “KHÔNG”
Truy vấn thứ tư:-
Chúng ta có thể chuyển từ chỉ mục 0 sang chỉ số 2 trong 3 bước tối đa:-
Bước 1:- chỉ mục 0 đến 1 (1 + 2 =3)
Bước 2:- chỉ mục 1 đến 2 (3 + 4 =7)
Bước 3:- Ở chỉ số 2 (7 + 4 =11)
Trong - Arr [] ={1, 2, 3, 3, 2}; Q [] [3] ={{0, 3, 2}, {1, 4, 3}};
Hết -
Truy vấn 1:KHÔNG
Truy vấn 2:10
Giải thích -
Truy vấn đầu tiên:-
Chúng ta không thể chuyển từ chỉ số 0 sang chỉ số 2 trong 1 bước tối đa. In “KHÔNG”
Truy vấn thứ hai:-
Chúng ta có thể chuyển từ chỉ mục 1 sang chỉ số 4 trong 3 bước tối đa:-
Bước 1:- chỉ mục 1 đến 2 (2 + 3 =5)
Bước 2:- chỉ mục 2 đến 3 (5 + 3 =8)
Bước 3:- chỉ số 3 đến 4 (8 + 2 =10)
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, chúng tôi sẽ sử dụng cây phân đoạn cho phạm vi từ lpos đến rpos để tìm giá trị lớn nhất có thể và tính tổng của tất cả các số bằng cách sử dụng tổng tiền tố.
-
Lấy mảng đầu vào Arr [] và ma trận truy vấn Q [] [].
-
Lấy sgTreee [5 * length] làm mảng để triển khai cây phân đoạn.
-
Lấy pSum [length] làm mảng tổng tiền tố.
-
Hàm createTree (int min, int max, int pos, int sgT [], int arr [], int len) được sử dụng để tạo giá trị trong cây phân đoạn.
-
Kiểm tra xem (min ==max) có nghĩa là nó là một nút lá. Đặt sgT [pos] =arr [max].
-
Lấy midd =(min + max) / 2.
-
Gọi createTree (min, midd, loc1, sgT, arr, len) và createTree (midd + 1, max, loc2, sgT, arr, len) cho các cây con trái và phải trong đó loc1 =2 * pos + 1 và loc2 =2 * pos + 2.
-
Lấy tmp1 =sgT [loc1] và tmp2 =sgT [loc2] và cập nhật sgT [pos] với tmp1 hoặc tmp2, tùy theo giá trị nào là tối đa.
-
Hàm preSum (int pSum4 [], int arr4 [], int len4) nhận mảng đầu vào và cập nhật mảng tiền tố bằng vòng lặp for.
-
Đối với mọi phần tử từ chỉ mục 1 đến chỉ mục cuối cùng, hãy cập nhật pSum4 [j] =pSum4 [j - 1] + arr4 [j];
-
Hàm resQuery (int len3, int arr3 [], int sgT3 [], int pSum3 [], int q1 [] [3], int qlen1) nhận tất cả các tham số đầu vào và in kết quả cho mỗi truy vấn.
-
Bên trong resQuery (), gọi solQuery (int lpos, int rpos, int k, int len2, int arr2 [], int sgT2 [], int pSum2 []) để giải quyết từng truy vấn một bằng vòng lặp for.
-
Hàm solQuery (int lpos, int rpos, int k, int len2, int arr2 [], int sgT2 [], int pSum2 []) giải quyết truy vấn và trả về kết quả.
-
Nếu rpos - lpos> k thì trả về -1 vì không có giải pháp nào khả thi.
-
Lấy maxVal =findMax (0, len2 - 1, lpos, rpos, 0, sgT2, arr2, len2);
-
Nếu maxVal <0 thì đặt maxVal là 0
-
Lấy biến sum =pSum2 [rpos].
-
Nếu lpos> 0 thì đặt sum - =pSum2 [lpos - 1] và result =sum + (k - (rpos - lpos)) * maxVal.
-
Trả về kết quả.
-
Hàm findMax (int start, int end, int min1, int max1, int pos1, int sgT1 [], int arr1 [], int len1) trả về giá trị lớn nhất giữa phạm vi lpos và rpos.
-
Nếu (min1 <=start) và (max1> =end) thì trả về sgT1 [pos1] vì có sự chồng chéo.
-
Nếu (end
max1) thì xảy ra ngoài phạm vi nên trả về INT_MIN. -
Tính lmax và rmax bằng cách sử dụng lệnh gọi đệ quy cho cây con trái và phải và trả về giá trị tối đa là hai.
-
Cuối cùng, kết quả sẽ được in cho mỗi truy vấn. “Không” nếu không có giải pháp
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
Query 1: 7 Query 2: NO Query 3: NO Query 4: 11