Chương trình C++ sắp xếp mảng theo dạng Max-Min (Lớn nhất - Nhỏ nhất)

Cho mảng số nguyên (có thể chưa sắp xếp). Nhiệm vụ: sắp xếp mảng tăng dần trước, sau đó xếp lại theo dạng: phần tử đầu là lớn nhất, thứ 2 là nhỏ nhất, thứ 3 là lớn nhì, thứ 4 là nhỏ nhì, và cứ thế.

Các trường hợp đầu vào/đầu ra mẫu

Đầu vào: int arr[] = {7, 5, 2, 3, 4, 9, 10, 5}

Đầu ra: Mảng trước (đã sort): 2 3 4 5 5 7 9 10
Mảng sau sắp xếp Max-Min: 10 2 9 3 7 4 5 5

Giải thích: Sort mảng → {2,3,4,5,5,7,9,10}. Lấy lần lượt: max (10), min (2), max2 (9), min2 (3), max3 (7), min3 (4), max4 (5), min4 (5).

Đầu vào: int arr[] = {2, 4, 1, 6, 7}

Đầu ra: Mảng trước: 1 2 4 6 7 → Mảng sau: 7 1 6 2 4

Phương pháp tiếp cận (O(1) không gian)

• Sort mảng bằng std::sort.
• Gọi Rearr_Max_Min(arr, size):
  • max = size-1, min = 0, max_val = arr[size-1] + 1.
  • Vòng lặp i từ 0 đến size-1:
    • Nếu i chẵn: arr[i] += (arr[max] % max_val) * max_val; max--;
    • Nếu i lẻ: arr[i] += (arr[min] % max_val) * max_val; min++;
  • Vòng lặp i: arr[i] = arr[i] / max_val; (lấy giá trị mới).

Ví dụ mã C++

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

void Rearr_Max_Min(int arr[], int size) {
    int max = size - 1;
    int min = 0;
    int max_val = arr[size - 1] + 1;
    for (int i = 0; i < size; i++) {
        if (i % 2 == 0) {
            arr[i] += (arr[max] % max_val) * max_val;
            max--;
        } else {
            arr[i] += (arr[min] % max_val) * max_val;
            min++;
        }
    }
    for (int i = 0; i < size; i++) {
        arr[i] = arr[i] / max_val;
    }
}

int main() {
    int arr[] = {7, 5, 2, 3, 4, 9, 10, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    sort(arr, arr + size);
    cout << "Array before Arrangement: ";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    Rearr_Max_Min(arr, size);
    cout << "\nRearrangement in maximum minimum form: ";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    return 0;
}

Đầu ra chương trình

Array before Arrangement: 2 3 4 5 5 7 9 10
Rearrangement of an array in maximum minimum form is: 10 2 9 3 7 4 5 5