Tối đa hóa tổng X+Y phần tử bằng cách chọn X từ mảng 1 và Y từ mảng 2 trong C++

Cho 2 mảng cùng kích thước N. Nhiệm vụ: chọn X phần tử từ mảng 1 và Y phần tử từ mảng 2 sao cho tổng các phần tử được chọn là lớn nhất.

Ví dụ 1

Input

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

Output – Tổng lớn nhất: 24

Giải thích: Chọn 2 số lớn nhất arr1: 5,4. Chọn 3 số lớn nhất arr2: 7,5,3. Tổng = 5+4+7+5+3 = 24.

Ví dụ 2

Input

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

Output – Tổng lớn nhất: 22

Giải thích: Chọn 1 số lớn nhất arr1: 16. Chọn 2 số lớn nhất arr2: 4,2. Tổng = 16+4+2 = 22.

Thuật toán

1. Sắp xếp cả 2 mảng tăng dần.
2. Lấy X phần tử cuối của arr1 (lớn nhất).
3. Lấy Y phần tử cuối của arr2 (lớn nhất).
4. Tính tổng.

Ví dụ code

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

int maxSum(int arr1[], int arr2[], int length, int X, int Y) {
    sort(arr1, arr1 + length);
    sort(arr2, arr2 + length);
    
    int sum = 0;
    // Lấy X phần tử lớn nhất của arr1
    for (int i = 0; i < X; i++) {
        sum += arr1[length - i - 1];
    }
    // Lấy Y phần tử lớn nhất của arr2
    for (int i = 0; i < Y; i++) {
        sum += arr2[length - i - 1];
    }
    return sum;
}

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

Kết quả

Maximized sum: 19

Giải thích: arr1 sort: [1,1,1,3,7] → lấy 3 lớn nhất: 7,3,1. arr2 sort: [1,1,2,3,5] → lấy 2 lớn nhất: 5,3. Tổng = 7+3+1+5+3 = 19.

Độ phức tạp: O(N log N) do sắp xếp. Có thể tối ưu O(N) dùng nth_element hoặc heap nếu N rất lớn.