ผลรวมของแฝดพิเศษที่มีองค์ประกอบจาก 3 อาร์เรย์ใน C++

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

แฝดพิเศษ เป็นแฝดสามชนิดพิเศษที่มีคุณสมบัติดังต่อไปนี้ −

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

และค่าของแฝดสามนั้นถูกกำหนดโดยสูตร -

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

ในการสร้างแฝดสามตัวนี้ เราจำเป็นต้องใช้องค์ประกอบหนึ่งจากอาร์เรย์ทั้งสามที่ได้รับมา

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล −

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

ผลผลิต

คำอธิบาย − มาหาค่าของแฝดพิเศษทั้งหมดกันเถอะ

(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

วิธีแก้ปัญหาง่ายๆ ก็คือการสร้างแฝดสามทั้งหมดจากอาร์เรย์ สำหรับแฝดพิเศษทั้งหมด คำนวณค่าโดยใช้สูตรข้างต้น แล้วบวกมันเข้าไปในตัวแปรผลรวมแล้วคืนค่าผลรวมสุดท้าย

ตัวอย่าง

โปรแกรมเพื่อแสดงวิธีแก้ปัญหา

#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 จากนั้นตรวจสอบองค์ประกอบที่ตรงตามข้อกำหนด triplets พิเศษสำหรับแต่ละองค์ประกอบของอาร์เรย์ 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 = (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 =จำนวนองค์ประกอบที่มากกว่า 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