Trong bài toán này, chúng ta có 3 mảng X, Y, Z. Nhiệm vụ của chúng ta là tạo một chương trình để tìm Tổng của các bộ ba đặc biệt có các phần tử từ 3 mảng.
Bộ ba đặc biệt là một loại bộ ba đặc biệt chứa thuộc tính sau -
Đối với (a, b, c):a ≤ b và b ≥ c, tức là phần tử ở giữa của bộ ba phải là phần tử chào hỏi hai phần tử còn lại.
Và, giá trị của bộ ba được cho bởi công thức -
f(a, b, c) = (a+b) * (b+c)
Để tạo bộ ba này, chúng ta cần sử dụng một phần tử của nhau trong ba mảng đã cho.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào -
X[] = {5, 9, 4} ; Y[] = {8, 6} ; Z[] = {7, 1} Đầu ra
Giải thích - Hãy tìm giá trị của tất cả các bộ ba đặc biệt.
(5, 8, 7) : value = (5+8) * (8+7) = 195 (5, 8, 1) : value = (5+8) * (8+1) = 117 (4, 8, 7) : value = (4+8) * (8+7) = 180 (4, 8, 1) : value = (4+8) * (8+1) = 108 (5, 6, 1) : value = (5+6) * (6+1) = 77 (4, 6, 1) : value = (4+6) * (6+1) = 70 Sum of special triplets = 747
Một giải pháp đơn giản cho vấn đề này là tạo tất cả các bộ ba từ mảng. Đối với tất cả các bộ ba đặc biệt, tính giá trị của nó bằng công thức trên. Và sau đó thêm chúng vào một biến tổng và trả về tổng cuối cùng.
Ví dụ
Chương trình minh họa giải pháp,
#include <iostream>
using namespace std;
int findSpecialTripletSum(int X[], int Y[], int Z[], int sizeX, int sizeY, int sizeZ) {
int sum = 0;
for (int i = 0; i < sizeX; i++) {
for (int j = 0; j < sizeY; j++) {
for (int k = 0; k < sizeZ; k++) {
if (X[i] <= Y[j] && Z[k] <= Y[j])
sum = sum + (X[i] + Y[j]) * (Y[j] + Z[k]);
}
}
}
return sum;
}
int main() {
int X[] = {5, 9, 4};
int Y[] = {8, 6};
int Z[] = {7, 1};
int sizeX = sizeof(X) / sizeof(X[0]);
int sizeY = sizeof(Y) / sizeof(Y[0]);
int sizeZ = sizeof(Z) / sizeof(Z[0]);
cout<<"Sum of special triplets = "<<findSpecialTripletSum(X, Y, Z,
sizeX, sizeY, sizeZ);
} Đầu ra
Sum of special triplets = 747
Một giải pháp khác hiệu quả hơn có thể là sắp xếp mảng X và Z. Sau đó, kiểm tra các phần tử đáp ứng yêu cầu bộ ba đặc biệt cho mỗi phần tử của mảng Y.
Vì vậy, đối với bất kỳ phần tử nào ở chỉ mục i của mảng Y, tức là Y [i]. Các phần tử của mảng X {x1, x2} và Z {z1, z2}, nhỏ hơn Y [i], sau đó
Tổng các giá trị,
S = (x1+Y[i])(Y[i]+z1) + (x1+Y[i])(Y[i]+z2) + (x2+Y[i])(Y[i]+z1) + (x2+Y[i])(Y[i]+z2) S = (x1+Y[i])(Y[i]+z1+Y[i]+z2) + (x2+Y[i])(Y[i]+z1+Y[i]+z2) S = (2Y[i] + x1 + x2)(2y[i] + z1 + z2)
N =số phần tử lớn hơn Y [i] trong X
M =số phần tử lớn hơn Y [i] trong Z
Sx =tổng các phần tử lớn hơn Y [i] trong X
Sz =tổng các phần tử lớn hơn Y [i] trong Z
S = (N*Y[i] + Sx) * (M*Y[i] + Sz)
Ví dụ
Chương trình minh họa giải pháp trên,
#include <bits/stdc++.h>
using namespace std;
int tripletSumCalc(int X[], int Y[], int Z[], int prefixSumA[], int prefixSumC[], int sizeA, int sizeB, int sizeC){
int totalSum = 0;
for (int i = 0; i < sizeB; i++) {
int currentElement = Y[i];
int n = upper_bound(X, X + sizeA, currentElement) - X;
int m = upper_bound(Z, Z + sizeC, currentElement) - Z;
if (n == 0 || m == 0)
continue;
totalSum += ((prefixSumA[n - 1] + (n * currentElement)) * (prefixSumC[m - 1] + (m * currentElement)));
}
return totalSum;
}
int* findPrefixSum(int* arr, int n) {
int* prefixSumArr = new int[n];
prefixSumArr[0] = arr[0];
for (int i = 1; i < n; i++)
prefixSumArr[i] = prefixSumArr[i - 1] + arr[i];
return prefixSumArr;
}
int findSpecialTripletSum(int A[], int B[], int C[], int sizeA, int sizeB, int
sizeC){
int specialTripletSum = 0;
sort(A, A + sizeA);
sort(C, C + sizeC);
int* prefixSumA = findPrefixSum(A, sizeA);
int* prefixSumC = findPrefixSum(C, sizeC);
return tripletSumCalc(A, B, C, prefixSumA, prefixSumC, sizeA, sizeB, sizeC);
}
int main() {
int A[] = {5, 9, 4};
int B[] = {8, 6};
int C[] = {7, 1};
int sizeA = sizeof(A) / sizeof(A[0]);
int sizeB = sizeof(B) / sizeof(B[0]);
int sizeC = sizeof(C) / sizeof(C[0]);
cout<<"Sum of special triplets = "<<findSpecialTripletSum(A, B, C, sizeA, sizeB, sizeC);
} Đầu ra
Sum of special triplets = 747