Tổng các bộ ba đặc biệt có phần tử từ 3 mảng trong C++

(5, 8, 7): (5+8)*(8+7) = 195
(5, 8, 1): (5+8)*(8+1) = 117
(4, 8, 7): (4+8)*(8+7) = 180
(4, 8, 1): (4+8)*(8+1) = 108
(5, 6, 1): (5+6)*(6+1) = 77
(4, 6, 1): (4+6)*(6+1) = 70
Tổng = 747

Cách đơn giản: sinh tất cả bộ ba, kiểm tra điều kiện, tính giá trị, cộng dồn.

Ví dụ

Chương trình minh họa:

#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

Cách hiệu quả hơn: sắp xếp X và Z. Với mỗi Y[i], dùng upper_bound tìm số phần tử ≤ Y[i] và tổng tiền tố của chúng.

N = số phần tử ≤ Y[i] trong X, M = số phần tử ≤ Y[i] trong Z.

Sx = tổng các phần tử ≤ Y[i] trong X, Sz = tổng trong Z.

Đóng góp của Y[i]: (N*Y[i] + Sx) * (M*Y[i] + Sz).

Ví dụ

Chương trình minh họa cách tối ưu:

#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