C++ Hoán vị mảng A sao cho A[i] > B[i] tối đa

Cho hai mảng A, B. Tìm hoán vị của A使得 số chỉ số i thỏa A[i] > B[i] là lớn nhất. Ví dụ:

Input: A=[12,22,41,13], B=[1,20,10,12] → Output: 12 22 41 13
Input: A=[2,5,9,7], B=[1,12,4,54] → Output: 2 7 5 9 (có thể có nhiều đáp án)

Giải bằng tham lam: sắp xếp cả hai, ghép phần tử A nhỏ nhất mà vẫn > B[i] vào vị trí i.

Phương pháp giải

Sắp xếp A và B (giữ chỉ số gốc). Duyệt B từ nhỏ đến lớn, với mỗi B[j] tìm A[i] > B[j] nhỏ nhất chưa dùng. Các A[i] còn lại đặt vào vị trí còn trống.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

int main() {
    int A[] = {2, 5, 9, 7};
    int B[] = {1, 12, 4, 54};
    int n = sizeof(A)/sizeof(int);

    vector<pair<int,int>> A_pair, B_pair;
    for (int i=0; i<n; i++) A_pair.push_back({A[i], i});
    for (int i=0; i<n; i++) B_pair.push_back({B[i], i});

    sort(A_pair.begin(), A_pair.end());
    sort(B_pair.begin(), B_pair.end());

    int ans[n];
    memset(ans, -1, sizeof(ans));
    vector<int> remaining;
    int i=0, j=0;

    while (i<n && j<n) {
        if (A_pair[i].first > B_pair[j].first) {
            ans[B_pair[j].second] = A_pair[i].first;
            i++; j++;
        } else {
            remaining.push_back(i);
            i++;
        }
    }

    j = 0;
    for (int i=0; i<n; i++)
        if (ans[i] == -1) ans[i] = A_pair[remaining[j++]].first;

    for (int i=0; i<n; i++) cout << ans[i] << " ";
    return 0;
}

Kết quả

2 7 5 9

Giải thích

Ghép tham lam: với mỗi B[j] từ nhỏ đến lớn, chọn A[i] nhỏ nhất > B[j]. Phần tử A không ghép được bỏ vào remaining, sau đó lấp đầy vị trí trống.

Kết luận

Đã giải bài toán hoán vị A thắng B tối đa bằng tham lam sau khi sắp xếp. Code C++ áp dụng cho các ngôn ngữ khác. Hy vọng hữu ích.