โปรแกรมตอบคำถามหาความต่างดัชนีของค่าที่เล็กที่สุด L และ R ใน C++

ให้อาร์เรย์ arr[] ขนาด n และ Q คำถาม แต่ละคำถามมี L, R ต้องการหาความต่างสัมบูรณ์ของดัชนีระหว่างค่าที่เล็กที่สุดอันดับ L และอันดับ R

ตัวอย่าง: arr = [8,4,1,5,2], Q=2, queries = {{2,4},{1,5}} คำถาม {2,4}: ค่าที่ 2 คือ 2 (ดัชนี 4), ค่าที่ 4 คือ 5 (ดัชนี 3) → |4-3|=1 คำถาม {1,5}: ค่าที่ 1 คือ 1 (ดัชนี 2), ค่าที่ 5 คือ 8 (ดัชนี 0) → |2-0|=2

วิธีแก้ปัญหา

1. สร้างอาร์เรย์คู่ (ค่า, ดัชนีต้นฉบับ)
2. เรียงตามค่า
3. แต่ละคำถาม: หา index ของอันดับ L และ R ในอาร์เรย์ที่เรียงแล้ว คำนวณความต่างดัชนีต้นฉบับ

ตัวอย่างโค้ด C++ (วิธี 1: ใช้ Pair)

#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] = {arr[i], 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 << "Query " << i+1 << ": " << result << endl;
    }
}

int main() {
    int arr[] = {8,4,1,5,2};
    int n = 5, Q = 2;
    int queries[][2] = {{2,4},{1,5}};
    solveAllQueries(arr, n, Q, queries);
    return 0;
}

ตัวอย่างโค้ด C++ (วิธี 2: ไม่ใช้ Pair)

#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], Rele = minArray[R-1];
    return abs(searchEle(arr, Lele, n) - searchEle(arr, Rele, n));
}

void solveAllQueries(int arr[], int n, int Q, int queries[][2]) {
    int minArray[n];
    copy(arr, arr+n, minArray);
    sort(minArray, minArray+n);
    for (int i = 0; i < Q; i++)
        cout << "Query " << i+1 << ": " 
             << findDifference(arr, minArray, n, queries[i][0], queries[i][1]) << endl;
}

int main() {
    int arr[] = {8,4,1,5,2};
    int n = 5, Q = 2;
    int queries[][2] = {{2,4},{1,5}};
    solveAllQueries(arr, n, Q, queries);
    return 0;
}

เอาต์พุต

Query 1: 1
Query 2: 2