เพิ่มผลรวม X+Y สูงสุดโดยเลือก X,Y องค์ประกอบจากอาร์เรย์ 1 และ 2 ใน C++

ได้รับอาร์เรย์ 2 ชุด ขนาด N ทั้งคู่ งานคือเลือก X องค์ประกอบจากอาร์เรย์ 1 และ Y องค์ประกอบจากอาร์เรย์ 2 ให้ผลรวมสูงสุด

ตัวอย่าง

ตัวอย่างที่ 1

Input:

arr1 = {1,2,3,4,5}, X=2
arr2 = {1,3,5,2,7}, Y=3

Output: 24

คำอธิบาย: เลือก 2 ตัวมากสุดของ arr1: 5,4 → เลือก 3 ตัวมากสุดของ arr2: 7,5,3 → รวม = 5+4+7+5+3 = 24

ตัวอย่างที่ 2

Input:

arr1 = {10,13,16,14}, X=1
arr2 = {4,1,2,1}, Y=2

Output: 22

คำอธิบาย: arr1 มากสุด: 16, arr2 มากสุด 2 ตัว: 4,2 → รวม = 16+4+2 = 22

แนวทางแก้ปัญหา

1. รับอาร์เรย์ arr1, arr2 และค่า X, Y
2. เรียงทั้งสองอาร์เรย์จากน้อยไปมาก (ascending)
3. เลือก X ตัวท้ายของ arr1 (ค่ามากสุด) และ Y ตัวท้ายของ arr2
4. รวมค่าที่เลือกทั้งหมด

ตัวอย่างโค้ด

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long maxSum(vector<int> arr1, vector<int> arr2, int X, int Y) {
    sort(arr1.begin(), arr1.end());
    sort(arr2.begin(), arr2.end());
    
    long long sum = 0;
    int n = arr1.size();  // สมมติขนาดเท่ากัน
    
    // เลือก X ตัวท้ายของ arr1
    for (int i = 0; i < X; i++) {
        sum += arr1[n - 1 - i];
    }
    // เลือก Y ตัวท้ายของ arr2
    for (int i = 0; i < Y; i++) {
        sum += arr2[n - 1 - i];
    }
    return sum;
}

int main() {
    vector<int> arr1 = {1, 1, 1, 3, 7};
    vector<int> arr2 = {1, 1, 2, 3, 5};
    int x = 3, y = 2;
    cout << "Maximized sum: " << maxSum(arr1, arr2, x, y) << endl;
    return 0;
}

ผลลัพธ์

Maximized sum: 19

arr1 เรียง: {1,1,1,3,7} → 3 ตัวท้าย: 7,3,1 = 11 arr2 เรียง: {1,1,2,3,5} → 2 ตัวท้าย: 5,3 = 8 รวม = 19

กรณีขนาดอาร์เรย์ไม่เท่ากัน

long long maxSumGeneral(vector<int> arr1, vector<int> arr2, int X, int Y) {
    sort(arr1.begin(), arr1.end());
    sort(arr2.begin(), arr2.end());
    
    long long sum = 0;
    for (int i = 0; i < X; i++) sum += arr1[arr1.size() - 1 - i];
    for (int i = 0; i < Y; i++) sum += arr2[arr2.size() - 1 - i];
    return sum;
}

ความซับซ้อน

• เวลา: O(N log N) จากการเรียงลำดับ (N = max(size1, size2))
• พื้นที่: O(1) เพิ่มเติม (in-place sort)

ขยายความ: หากต้องเลือกจากอาร์เรย์เดียว (X+Y จาก arr1+arr2 รวม)

รวมอาร์เรย์ทั้งสอง เรียง แล้วเลือก X+Y ตัวท้าย