Số lớn nhất bằng cách sắp xếp số theo thứ tự nhất định trong C++

Trong bài toán này, cho một mảng số, cần tìm giá trị lớn nhất có thể tạo bằng cách sắp xếp chúng theo một cách nhất định. Điều kiện sắp xếp là thứ tự của số chẵn và lẻ phải giữ nguyên, tức là thứ tự của tất cả số chẵn không thể thay đổi.

Hãy lấy ví dụ để hiểu khái niệm tốt hơn:

Input: {17, 80, 99, 27, 14, 22}
Output: 801799271422
Giải thích: Thứ tự số chẵn và lẻ là:
Chẵn: 80 14 22
Lẻ: 17 99 27

Ở đây 99 là số lớn nhất nhưng 17 đứng trước nó trong thứ tự số lẻ, nên ta xem xét 80 trước và sau đó sắp xếp tuần tự như: 80 17 99 27 14 22

Vì đã hiểu bài toán, hãy thử sinh giải pháp. Ở đây không thể dùng sắp xếp giảm dần cổ điển vì ràng buộc về trình tự chẵn/lẻ. Vì vậy, phải duy trì trình tự này và kiểm tra lớn hơn của các phần tử đầu tiên của trình tự chẵn và lẻ. Và tiếp tục như vậy. Hãy xem thuật toán làm rõ hơn.

Thuật toán

Bước 1: Tạo hai cấu trúc, một cho chẵn, một cho lẻ, để duy trì trình tự.
Bước 2: Lấy một phần tử từ mỗi cấu trúc và kiểm tra tổ hợp nào tạo số lớn hơn. Ví dụ, nếu E là số chẵn và O là số lẻ ở đỉnh cấu trúc. Ta kiểm tra lớn hơn của EO và OE.
Bước 3: Đặt tổ hợp lớn hơn vào trình tự cuối cùng.
Bước 4: In trình tự cuối cùng.

Ví dụ

Bây giờ, hãy tạo chương trình dựa trên thuật toán này.

#include <bits/stdc++.h>
using namespace std;
string merge(vector<string> arr1, vector<string> arr2) {
    int n1 = arr1.size();
    int n2 = arr2.size();
    int i = 0, j = 0;
    string big = "";
    while (i < n1 && j < n2) {
        if ((arr1[i] + arr2[j]).compare((arr2[j] + arr1[i])) > 0)
            big += arr1[i++];
        else
            big += arr2[j++];
    }
    while (i < n1) big += arr1[i++];
    while (j < n2) big += arr2[j++];
    return big;
}
string largestNumber(vector<string> arr, int n) {
    vector<string> even, odd;
    for (int i = 0; i < n; i++) {
        int lastDigit = arr[i].at(arr[i].size() - 1) - '0';
        if (lastDigit % 2 == 0)
            even.push_back(arr[i]);
        else
            odd.push_back(arr[i]);
    }
    string biggest = merge(even, odd);
    return biggest;
}
int main() {
    vector<string> arr;
    arr.push_back("17");
    arr.push_back("80");
    arr.push_back("99");
    arr.push_back("27");
    arr.push_back("14");
    arr.push_back("22");
    int n = arr.size();
    cout<<"Số lớn nhất có thể từ mảng là = "<<largestNumber(arr, n);
    return 0;
}

Kết quả

Số lớn nhất có thể từ mảng là = 801799271422