ผลรวมของ Special Triplets จาก 3 อาร์เรย์ใน C++

ในปัญหานี้ เราได้รับ 3 อาร์เรย์ X, Y, Z ภารกิจคือการสร้างโปรแกรมเพื่อหาผลรวมของ Special Triplets ที่มีองค์ประกอบมาจาก 3 อาร์เรย์

Special Triplet คือ triplet พิเศษที่มีคุณสมบัติดังนี้ −

สำหรับ (a, b, c): a ≤ b และ b ≥ c คือ องค์ประกอบกลางของ triplet ต้องมากกว่าหรือเท่ากับอีกสององค์ประกอบ

และ ค่าของ triplet กำหนดโดยสูตร −

f(a, b, c) = (a+b) * (b+c)

เพื่อสร้าง triplet นี้ เราต้องใช้องค์ประกอบหนึ่งจากแต่ละอาร์เรย์ของ 3 อาร์เรย์ที่กำหนด

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต −

X[] = {5, 9, 4}; Y[] = {8, 6}; Z[] = {7, 1}

เอาต์พุต

คำอธิบาย − มาหาค่าของ Special Triplets ทั้งหมด

(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

วิธีง่ายคือสร้าง triplet ทุกคูณที่เป็นไปได้จากอาร์เรย์ สำหรับ special triplets ทุกตัว คำนวณค่าด้วยสูตรข้างต้น แล้วบวกเข้าไปในตัวแปร sum และคืนค่าผลรวมสุดท้าย

ตัวอย่างโปรแกรม (วิธีแบบง่าย)

#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);
}

เอาต์พุต

Sum of special triplets = 747

วิธีที่มีประสิทธิภาพมากกว่า คือการจัดเรียงอาร์เรย์ X และ Z แล้วตรวจสอบองค์ประกอบที่ตรงตามเงื่อนไข special triplet สำหรับแต่ละองค์ประกอบของอาร์เรย์ Y

ดังนั้น สำหรับองค์ประกอบที่ดัชนี i ของอาร์เรย์ Y คือ Y[i] องค์ประกอบของอาร์เรย์ X {x1, x2} และ Z {z1, z2} ที่น้อยกว่า Y[i] ผลรวมของค่าคือ

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 = (2Y[i] + x1 + x2)(2Y[i] + z1 + z2)

N = จำนวนองค์ประกอบที่น้อยกว่าหรือเท่ากับ Y[i] ใน X

M = จำนวนองค์ประกอบที่น้อยกว่าหรือเท่ากับ Y[i] ใน Z

Sx = ผลรวมขององค์ประกอบที่น้อยกว่าหรือเท่ากับ Y[i] ใน X

Sz = ผลรวมขององค์ประกอบที่น้อยกว่าหรือเท่ากับ Y[i] ใน Z

S = (N·Y[i] + Sx) * (M·Y[i] + Sz)

ตัวอย่างโปรแกรม (วิธีที่มีประสิทธิภาพ)

#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);
}

เอาต์พุต

Sum of special triplets = 747