เราได้รับอาร์เรย์ Arr[] ที่มีจำนวนเต็มและอาร์เรย์ 2 มิติ Q ที่มีข้อความค้นหา การสืบค้นแต่ละรายการประกอบด้วย 3 ค่า ได้แก่ lpos, rpos และ K โดยสามารถย้ายจากดัชนี i ไปยังดัชนีถัดไป i+1 ในขั้นตอนเดียวหรือคงอยู่ในดัชนีนั้น สามารถย้ายจาก lpos เป็น rpos ได้สูงสุด K ขั้นเท่านั้น เพิ่มตัวเลขทั้งหมดในแต่ละขั้นตอนรวมทั้งหมายเลขซ้ายสุด เป้าหมายคือการเพิ่มผลรวมสูงสุดในการเคลื่อนไหว K สูงสุด หากไม่มีการเคลื่อนไหวจาก lpos ถึง rpos ในขั้นตอน K ให้พิมพ์ "ไม่" ให้เราเข้าใจมากขึ้น
ให้เราดูสถานการณ์อินพุตเอาต์พุตต่างๆ สำหรับสิ่งนี้ -
ใน − 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
คำอธิบาย −
คำถามแรก:-
เราสามารถย้ายจากดัชนี 0 เป็น 2 ได้สูงสุด 2 ขั้นตอน:-
ขั้นตอนที่ 1:- ดัชนี 0 ถึง 1 ( 1+2=3 )
ขั้นตอนที่ 2:- ดัชนี 1 ถึง 2 ( 3+4=7 )
คำถามที่สอง:-
เราไม่สามารถย้ายจากดัชนี 0 เป็น 2 ใน 1 ขั้นตอนสูงสุด พิมพ์ “ไม่”
คำค้นหาที่สาม:-
เราไม่สามารถย้ายจากดัชนี 3 เป็น 3 ใน 1 ขั้นตอนสูงสุด พิมพ์ “ไม่”
คำถามที่สี่:-
เราสามารถย้ายจากดัชนี 0 เป็น 2 ได้สูงสุด 3 ขั้นตอน:-
ขั้นตอนที่ 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
คำอธิบาย −
คำถามแรก:-
เราไม่สามารถย้ายจากดัชนี 0 เป็น 2 ใน 1 ขั้นตอนสูงสุด พิมพ์ “ไม่”
คำถามที่สอง:-
เราสามารถย้ายจากดัชนี 1 เป็น 4 ได้สูงสุด 3 ขั้นตอน:-
ขั้นตอนที่ 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) ใช้เพื่อสร้างค่าในแผนผังกลุ่ม
-
ตรวจสอบว่า (ต่ำสุด ==สูงสุด) ซึ่งหมายความว่าเป็นโหนดปลายสุด ตั้งค่า sgT[pos] =arr[สูงสุด].
-
Take mid =(ต่ำสุด + สูงสุด) / 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] และอัปเดต sgT[pos] ด้วย tmp1 หรือ tmp2 แล้วแต่จำนวนใดจะสูงสุด
-
ฟังก์ชัน preSum(int pSum4[], int arr4[], int len4) รับอาร์เรย์อินพุตและอัปเดตอาร์เรย์นำหน้าโดยใช้ for loop
-
สำหรับทุกองค์ประกอบตั้งแต่ดัชนี 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[]) เพื่อแก้ปัญหาแต่ละรายการโดยใช้การวนซ้ำ
-
ฟังก์ชัน 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] และ 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] เนื่องจากมีการทับซ้อนกัน
-
หาก (สิ้นสุด
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
