Tối đa hóa giá trị số A bằng cách thay thế chữ số bằng chữ số của B trong C++

Nhiệm vụ: tối đa hóa giá trị của số A (dạng chuỗi) bằng cách thay thế một số chữ số của A bằng chữ số từ số B. Mỗi chữ số của B chỉ được dùng một lần. Không thay thế nếu không làm tăng giá trị A.

Ví dụ 1

Input

A = "1221", B = "1211"

Output

Maximum value of A: 2221

Giải thích: Lấy '2' từ B thay cho '1' đầu tiên của A. Các vị trí khác không thể tăng thêm.

Ví dụ 2

Input

A = "1002", B = "3200"

Output

Maximum value of A: 3202

Thuật toán tham lam

1. Sắp xếp các chữ số của B theo thứ tự tăng dần.
2. Duyệt A từ trái sang phải (chữ số quan trọng nhất trước).
3. Duyệt B từ phải sang trái (chữ số lớn nhất trước).
4. Nếu chữ số B > chữ số A tại vị trí hiện tại: thay thế, dùng chữ số B đó (giảm con trỏ B), chuyển vị trí A tiếp theo.
5. Nếu không: giữ nguyên chữ số A, chuyển vị trí A tiếp theo.
6. Dừng khi hết chữ số B hoặc hết chữ số A.

Ví dụ code

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

string maximizeValue(string str1, string str2) {
    // Sắp xếp B tăng dần để lấy từ cuối (lớn nhất) dễ dàng
    sort(str2.begin(), str2.end());
    
    int len1 = str1.length();
    int len2 = str2.length();
    int j = len2 - 1; // Con trỏ B (từ cuối - lớn nhất)
    
    for (int i = 0; i < len1; i++) {
        if (j < 0) break; // Hết chữ số B
        if (str2[j] > str1[i]) {
            str1[i] = str2[j];
            j--; // Đã dùng chữ số này
        }
    }
    return str1;
}

int main() {
    string a = "1204";
    string b = "4521";
    cout << maximizeValue(a, b) << endl;
    return 0;
}

Kết quả

5424

Giải thích: B sắp xếp: "1245". Duyệt A="1204": - i=0: '1' < '5' (B[3]) → thay '5', j=2 - i=1: '2' < '4' (B[2]) → thay '4', j=1 - i=2: '0' < '2' (B[1]) → thay '2', j=0 - i=3: '4' > '1' (B[0]) → giữ '4' Kết quả: "5424"

Độ phức tạp: O(n log n + m log m) do sắp xếp, n,m độ dài chuỗi.