Hướng dẫn giải

1. Nhận xét quan trọng

Vì các phần tử đôi một khác nhau và ~x~ chắc chắn có mặt trong dãy, khi sắp xếp tăng dần:

• Mọi số nhỏ hơn ~x~ đứng trước ~x~.
• Mọi số lớn hơn ~x~ đứng sau ~x~.

Do đó, vị trí của ~x~ bằng số phần tử nhỏ hơn ~x~ cộng 1.

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

Không cần sắp xếp cả dãy. Ta chỉ cần duyệt từng phần tử và đếm bao nhiêu số nhỏ hơn ~x~.

Vì ~x~ được nhập sau dãy, ta lưu dãy vào mảng trước rồi mới thực hiện đếm.

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

1. Nhập ~n~ và ~n~ phần tử của mảng ~a~.
2. Nhập ~x~.
3. Khởi tạo ~dem = 0~.
4. Duyệt mảng: nếu ~a[i] < x~ thì tăng ~dem~ lên 1.
5. In ra ~dem + 1~.

4. Minh họa

Với dãy 2 3 1 5 4 và ~x = 4~:

Có 3 phần tử nhỏ hơn 4 nên vị trí cần tìm là ~3 + 1 = 4~.

5. Độ phức tạp

• Thời gian: ~O(n)~ vì chỉ duyệt mảng một lần.
• Bộ nhớ: ~O(n)~ để lưu mảng trước khi đọc ~x~.

Cách này hiệu quả hơn việc sắp xếp toàn bộ dãy với độ phức tạp ~O(n \log n)~.

Code mẫu C++17

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

int n, x, dem;
int a[100005];

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

    dem = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] < x) dem++;
    }

    cout << dem + 1 << endl;
    return 0;
}

Lưu ý cho học sinh

• Không nhầm chỉ số mảng với vị trí kết quả: Mảng C++ bắt đầu từ chỉ số 0, nhưng đề yêu cầu vị trí bắt đầu từ 1.
• Không cần sắp xếp: Chỉ đếm các phần tử nhỏ hơn ~x~ là đủ.
• Không dùng >= hoặc <= khi đếm: Phải đếm đúng các phần tử nhỏ hơn ~x~.
• Có số âm: Phép so sánh a[i] < x vẫn hoạt động bình thường.
• Trường hợp ~n = 1~: Kết quả luôn bằng 1.

Bài tập mở rộng

Nếu dãy có thể chứa nhiều phần tử bằng ~x~, hãy xác định vị trí đầu tiên mà ~x~ có thể xuất hiện sau khi sắp xếp tăng dần. Khi đó, công thức đếm số phần tử nhỏ hơn ~x~ rồi cộng 1 vẫn đúng.