home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ลดค่า Max-Min ของ Triplet จาก 3 Sorted Arrays ใน C++

แนวคิด

กำหนด 3 sorted arrays A, B, C ขนาดไม่จำเป็นต้องเท่ากัน หา triplet (A[i], B[j], C[k]) ที่ทำให้ max(A[i], B[j], C[k]) - min(A[i], B[j], C[k]) มีค่าน้อยที่สุด

ตัวอย่าง: - A=[2,5,6,9,11], B=[7,10,16], C=[3,4,7,7] → min diff = 1 (เลือก 6,7,7) - A=[6,9,11,16], B=[7,10,16,79,90], C=[3,4,7,7,9,9,11] → min diff = 1 (เลือก 11,10,11)

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

  1. เริ่มจาก index สุดท้ายของแต่ละ array (ค่าสูงสุด)
  2. คำนวณ diff = max - min อัพเดทคำตอบ
  3. ลด index ของ array ที่มีค่า max (เพราะลด max เท่านั้นที่ลด diff ได้)
  4. ทำซ้ำจนกว่าจะหมด array ใด array หนึ่ง

Complexity: O(N1+N2+N3)

ตัวอย่างโค้ด C++

#include<bits/stdc++.h>
using namespace std;

int solve(int A1[], int B1[], int C1[], int i1, int j1, int k1) {
    int min_diff = abs(max(A1[i1], max(B1[j1], C1[k1])) - min(A1[i1], min(B1[j1], C1[k1])));
    while(i1 != -1 && j1 != -1 && k1 != -1) {
        int current_diff = abs(max(A1[i1], max(B1[j1], C1[k1])) - min(A1[i1], min(B1[j1], C1[k1])));
        if(current_diff < min_diff) min_diff = current_diff;
        int max_term = max(A1[i1], max(B1[j1], C1[k1]));
        if(A1[i1] == max_term) i1 -= 1;
        else if(B1[j1] == max_term) j1 -= 1;
        else k1 -= 1;
    }
    return min_diff;
}

int main() {
    int D1[] = { 5, 8, 10, 15 };
    int E1[] = { 6, 9, 15, 78, 89 };
    int F1[] = { 2, 3, 6, 6, 8, 8, 10 };
    int nD = sizeof(D1) / sizeof(D1[0]);
    int nE = sizeof(E1) / sizeof(E1[0]);
    int nF = sizeof(F1) / sizeof(F1[0]);
    cout << solve(D1, E1, F1, nD-1, nE-1, nF-1);
    return 0;
}

ผลลัพธ์

1