ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของขนาด n และ Q คิวรีแต่ละรายการประกอบด้วย 2 ค่า L และ R งานของเราคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นเพื่อคืนค่าความแตกต่างที่แน่นอนระหว่างตัวเลขที่น้อยที่สุดใน L-th และ R-th จำนวนน้อยที่สุด
คำอธิบายปัญหา − เพื่อแก้ปัญหาแต่ละคำถาม เราจำเป็นต้องค้นหาดัชนีของ Lth ที่เล็กที่สุดและ Rth ตัวเลขที่น้อยที่สุด และหาความแตกต่างระหว่างดัชนีเหล่านี้
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {8, 4, 1, 5, 2} Q = 2 Queries[][] = {{2, 4}, {1, 5}} ผลลัพธ์
1 2
คำอธิบาย
For {2, 4}: 2nd smallest element is 2 whose index is 4
4th smallest element is 5 whose index is 3 Difference = 4 - 3 = 1
For {1, 5} Smallest element is 1 whose index is 2
5th smallest element is 8 whose index is 0 Difference = 2 - 0 = 2 แนวทางการแก้ปัญหา
ในการแก้ปัญหา เราจะสร้างคู่ที่จะเก็บดัชนีและค่าขององค์ประกอบอาร์เรย์ และค้นหาองค์ประกอบที่เล็กที่สุดลำดับที่ i สำหรับทั้งค่า L และ R ของแต่ละแบบสอบถาม จากนั้นพิมพ์ผลต่างสัมบูรณ์ของดัชนี
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) {
pair<int, int> arrayIndex[n];
for (int i = 0; i < n; i++) {
arrayIndex[i].first = arr[i];
arrayIndex[i].second = i;
}
sort(arrayIndex, arrayIndex + n);
for (int i = 0; i < Q; i++){
int result = ( abs(arrayIndex[queries[i][0] - 1].second - arrayIndex[queries[i][1] - 1].second) );
cout<<"For Query "<<(i+1)<<": Difference is "<<result<<endl;
}
}
int main() {
int arr[] = { 8, 4, 1, 5, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }};
solveAllQueries(arr, n, Q, queries);
return 0;
} ผลลัพธ์
For Query 1: Difference is 1 For Query 2: Difference is 2
โปรแกรมนี้ใช้โครงสร้างข้อมูลคู่ แต่มีวิธีแก้ปัญหาที่สามารถค้นหาความแตกต่างโดยไม่ต้องใช้มัน สำหรับสิ่งนี้ เราจะใช้อาร์เรย์ที่จะจัดเก็บองค์ประกอบในลำดับจากน้อยไปมาก แล้วหาองค์ประกอบที่เล็กที่สุดสำหรับทั้งสองค่าของ L และ R สำหรับแต่ละแบบสอบถาม จากนั้นค้นหาความแตกต่างของดัชนี
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int searchEle(int arr[], int ele, int n){
for(int i = 0; i < n; i++)
if(arr[i] == ele)
return i;
return -1;
}
int findDifference(int arr[], int minArray[], int n, int L, int R){
int Lele = minArray[L-1];
int Rele = minArray[R-1];
int index1 = searchEle(arr, Lele, n);
int index2 = searchEle(arr, Rele, n);
return abs(index1 - index2);
}
void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) {
int minArray[n];
for (int i = 0; i < n; i++)
minArray[i] = arr[i];
sort(minArray, minArray + n);
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1)<<": Difference is "<<findDifference(arr, minArray, n, queries[i][0], queries[i][1])<<endl;
}
}
int main() {
int arr[] = { 8, 4, 1, 5, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }};
solveAllQueries(arr, n, Q, queries); return 0;
} ผลลัพธ์
For Query 1: Difference is 1 For Query 2: Difference is 2
