Hướng dẫn giải

1. Phân tích bài toán

Ta cần thực hiện hai công việc:

1. Đưa số ~k~ vào dãy ban đầu.
2. Sắp xếp toàn bộ ~n+1~ phần tử theo thứ tự giảm dần.

Dãy ban đầu không được cho là đã sắp xếp, vì vậy không thể chỉ tìm vị trí để chèn ~k~ rồi in ngay.

2. Ý tưởng thuật toán

Sử dụng mảng (hoặc vector) để lưu các số. Sau khi nhập ~n~ phần tử, thêm ~k~ vào cuối dãy. Dùng hàm sort với tiêu chí greater<int>() để sắp xếp giảm dần, rồi in kết quả.

3. Các bước thực hiện

• Bước 1: Nhập ~n~ và ~n~ phần tử của dãy.
• Bước 2: Nhập ~k~, thêm ~k~ vào dãy bằng push_back(k).
• Bước 3: Sắp xếp giảm dần bằng sort(a.begin(), a.end(), greater<int>()).
• Bước 4: Duyệt dãy và in các phần tử, cách nhau một dấu cách.

4. Minh họa

Với ~n=3~, dãy ban đầu là 1 5 2 và ~k=4~:

• Sau khi thêm: 1 5 2 4.
• Sau khi sắp xếp giảm dần: 5 4 2 1.

Vậy kết quả là 5 4 2 1.

5. Độ phức tạp

• Nhập và thêm phần tử: ~O(n)~.
• Sắp xếp ~n+1~ phần tử: ~O(n\log n)~.
• In kết quả: ~O(n)~.

Tổng độ phức tạp thời gian: ~O(n\log n)~.

Độ phức tạp bộ nhớ: ~O(n)~ để lưu dãy.

6. Chương trình C++ tham khảo

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

int n, k;
vector<int> a;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a.push_back(x);
    }

    cin >> k;
    a.push_back(k);

    sort(a.begin(), a.end(), greater<int>());

    for (int i = 0; i < (int)a.size(); i++) {
        if (i > 0) cout << " ";
        cout << a[i];
    }
    cout << endl;
    return 0;
}

7. Lưu ý khi làm bài

• Dãy có thể chứa số âm, số ~0~ và các phần tử trùng nhau; không được loại bỏ phần tử trùng.
• Số ~k~ cũng có thể bằng một phần tử đã có trong dãy.
• Dùng greater<int>() để sắp xếp giảm dần; mặc định sort sắp xếp tăng dần.
• Với ~n \le 10^5~, thuật toán sắp xếp ~O(n\log n)~ đáp ứng tốt giới hạn đề bài.