Tối thiểu hóa chênh lệch max-min của triplet từ 3 mảng đã sắp xếp trong C++

Khái niệm

Cho 3 mảng A, B, C đã sắp xếp (kích thước có thể khác). Tìm min giá trị của max(A[i],B[j],C[k]) - min(A[i],B[j],C[k]).

Ví dụ 1: A=[2,5,6,9,11], B=[7,10,16], C=[3,4,7,7] → 1 (chọn 6,7,7).

Ví dụ 2: A=[6,9,11,16], B=[7,10,16,79,90], C=[3,4,7,7,9,9,11] → 1 (chọn 11,10,11).

Phương pháp

Bắt đầu từ phần tử lớn nhất của mỗi mảng (chỉ số cuối). Lặp:

1. Tính diff = max - min, cập nhật min_diff.
2. Chỉ có cách giảm diff là giảm phần tử lớn nhất → giảm chỉ số của mảng chứa max.
3. Lặp cho đến khi một mảng hết phần tử.

Ví dụ (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--;
        else if(B1[j1]==max_term) j1--;
        else k1--;
    }
    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};
    cout<<solve(D1,E1,F1,sizeof(D1)/sizeof(D1[0])-1,
               sizeof(E1)/sizeof(E1[0])-1,
               sizeof(F1)/sizeof(F1[0])-1);
    return 0;
}

Đầu ra

1