Hiểu bài toán

Bài toán yêu cầu sắp xếp mảng tăng dần nhưng giữ nguyên giá trị và vị trí của phần tử đầu tiên (index 0) và cuối cùng (index n-1). Chỉ các phần tử nằm giữa chúng (từ index 1 đến index n-2) mới được phép sắp xếp lại.

Các cách tiếp cận

Cách Bubble Sort (Sáp xuất) trực tiếp

#include <stdio.h>
int main() {
    int n; scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    // Sắp xếp từ index 1 đến n-2
    for (int i = 1; i < n - 1; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            if (a[i] > a[j]) {
                int tmp = a[j];
                a[j] = a[i];
                a[i] = tmp;
            }
        }
    }

    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Đây là cách tiếp cận đơn giản nhất sử dụng thuật toán Bubble Sort. Chương trình duyệt qua các phần tử từ chỉ số 1 đến n-2 và hoán đổi nếu phần tử trước lớn hơn phần tử sau. Với n tối đa 10^4, độ phức tạp O(n^2) vẫn có thể chấp nhận được nhưng không tối ưu.

Cách Quick Sort (Hand-written)

#include <stdio.h>
int Partition(int a[], int l, int r) {
    int pivot = a[r];
    int i = l - 1;
    for (int j = l; j < r; j++) {
        if (pivot >= a[j]) {
            ++i;
            int tmp = a[j]; a[j] = a[i]; a[i] = tmp;
        }
    }
    i++;
    int tmp = a[r]; a[r] = a[i]; a[i] = tmp;
    return i;
}
void quicksort(int a[], int l, int r) {
    if (l < r) {
        int m = Partition(a, l, r);
        quicksort(a, l, m - 1);
        quicksort(a, m + 1, r);
    }
}
int main() {
    int n; scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    // Sắp xếp từ index 1 đến n-2
    quicksort(a, 1, n - 2);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(log n)

Sử dụng thuật toán Quick Sort thủ công để sắp xếp dãy con từ index 1 đến n-2. Cách này hiệu quả hơn Bubble Sort đáng kể. Tuy nhiên, việc viết lại Quick Sort có thể gây lỗi nếu không cẩn thận với điều kiện dừng và chia mảng.

Cách C Library qsort (Optimal)

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    long long x = *(long long *)a;
    long long y = *(long long *)b;
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

int main() {
    int n;
    scanf("%d", &n);
    long long A[n];
    for (int i = 0; i < n; i++) scanf("%lld", &A[i]);

    if (n > 2) {
        // qsort(start_address, num_elements, element_size, compare_func)
        qsort(A + 1, n - 2, sizeof(long long), cmp);
    }

    for (int i = 0; i < n; i++) {
        printf("%lld", A[i]);
        if (i < n - 1) printf(" ");
    }
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Sử dụng hàm qsort có sẵn trong thư viện chuẩn của C. Đây là cách hiệu quả nhất và ngắn gọn nhất. Lưu ý: cần dùng long long do giới hạn giá trị phần tử lên tới 10^9. Tham số A + 1 truyền vào hàm qsort giúp chỉ sắp xếp từ phần tử thứ 2 trở đi (index 1).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán là biến thể của sắp xếp: giữ nguyên 2 đầu, sắp xếp中间. Cách tiếp cận đơn giản nhất là sắp xếp mảng con từ index 1 đến index n-2.
• Sử dụng thư viện chuẩn (qsort trong C, sort trong C++) là cách tối ưu nhất về độ tin cậy và hiệu năng trong lập trình thi đấu.
• Cần chú ý đến kiểu dữ liệu (int hay long long) dựa trên giới hạn giá trị đầu vào (|A| <= 10^9).

Lỗi thường gặp

• Sử dụng sai kiểu dữ liệu: Nếu dùng int nhưng giá trị input > 210^9 (trong C++ thường là 210^9) hoặc > 10^9 (theo đề bài) nhưng vẫn muốn an toàn, nên dùng long long.
• Lỗi chỉ số mảng (Index out of bounds): Khi gọi hàm sắp xếp, cần đảm bảo khoảng [1, n-2] hợp lệ. Nếu n=3, chỉ số hợp lệ duy nhất là 1. Cần kiểm tra if (n > 2) trước khi sắp xếp để tránh lỗi với các mảng quá ngắn.
• Đề bài yêu cầu giữ nguyên vị trí đầu và cuối, nhưng một số giải pháp sai có thể sắp xếp toàn bộ mảng hoặc chỉ sắp xếp một phần không đúng.