แนวคิด
สำหรับอาร์เรย์ที่จัดเรียงสามชุด A, B และ C ไม่จำเป็นต้องมีขนาดเท่ากัน ให้คำนวณค่าต่ำสุด กล่าวคือ ค่าความแตกต่างสัมบูรณ์ขั้นต่ำระหว่างจำนวนสูงสุดและต่ำสุดของ triplet A[i],B[j], C[k] ดังกล่าว ว่าอยู่ภายใต้อาร์เรย์ A, B และ C ตามลำดับ เช่น ย่อเล็กสุด (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 ]
ผลผลิต −
1
คำอธิบาย
เมื่อเราเลือก A[i] =6 , B[j] =7, C[k] =7 เราจะได้ค่าความแตกต่างขั้นต่ำเป็น max(A[i], B[j], C[k]) - min( A[i], B[j], C[k])) =|7-6| =1
ป้อนข้อมูล −
A = [ 6, 9, 11, 16 ] B = [ 7, 10, 16, 79, 90 ] C = [ 3, 4, 7, 7, 9, 9, 11 ]
ผลผลิต −
1
คำอธิบาย −
เมื่อเราเลือก A[i] =11 , b[j] =10, C[k] =11 เราได้รับผลต่างขั้นต่ำเป็น max(A[i], B[j], C[k]) - min( A[i], B[j], C[k]))=|11-10| =1
วิธีการ
เริ่มต้นด้วยองค์ประกอบที่สูงที่สุดในแต่ละอาร์เรย์ A, B &C ติดตามตัวแปรเพื่ออัปเดตคำตอบในเวลาของแต่ละขั้นตอนที่จะปฏิบัติตาม
ด้วยความเคารพในแต่ละขั้นตอน วิธีเดียวที่เป็นไปได้ในการลดความแตกต่างคือการลดองค์ประกอบสูงสุดจากองค์ประกอบทั้งสาม
ด้วยเหตุนี้ ให้ไปที่องค์ประกอบสูงสุดถัดไปในอาร์เรย์ที่มีองค์ประกอบสูงสุดสำหรับขั้นตอนนี้ และอัปเดตตัวแปรคำตอบ
เราต้องทำซ้ำขั้นตอนนี้จนกว่าอาร์เรย์ที่มีองค์ประกอบสูงสุดจะยุติลง
ตัวอย่าง(C++)
// รหัส C++ สำหรับวิธีการด้านบน
#include<bits/stdc++.h>
usingnamespacestd;
intsolve(intA1[], intB1[], intC1[], inti1, intj1, intk1) {
intmin_diff, current_diff, max_term;
// calculating min difference from last
// index of lists
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) {
current_diff = abs(max(A1[i1], max(B1[j1], C1[k1]))
- min(A1[i1], min(B1[j1], C1[k1])));
// checking condition
if(current_diff < min_diff)
min_diff = current_diff;
// calculating max term from list
max_term = max(A1[i1], max(B1[j1], C1[k1]));
if(A1[i1] == max_term)
i1 -= 1;
elseif(B1[j1] == max_term)
j1 -= 1;
else
k1 -= 1;
}
returnmin_diff;
}
intmain() {
intD1[] = { 5, 8, 10, 15 };
intE1[] = { 6, 9, 15, 78, 89 };
intF1[] = { 2, 3, 6, 6, 8, 8, 10 };
intnD = sizeof(D1) / sizeof(D1[0]);
intnE = sizeof(E1) / sizeof(E1[0]);
intnF = sizeof(F1) / sizeof(F1[0]);
cout << solve(D1, E1, F1, nD-1, nE-1, nF-1);
return0;
} ผลลัพธ์
1
