Hướng dẫn giải

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

Ta cần tìm hai giá trị ~mn~ và ~mx~ lần lượt là số nhỏ nhất và số lớn nhất trong dãy. Sau đó, duyệt lại dãy để in ra mọi vị trí có giá trị bằng ~mn~ hoặc ~mx~.

Vì vị trí được đánh số từ ~1~ nên có thể lưu các phần tử vào mảng từ chỉ số ~1~ đến ~n~. Duyệt từ trái sang phải sẽ tự động cho các vị trí theo thứ tự tăng dần.

Chú ý: Nếu tất cả phần tử bằng nhau thì ~mn = mx~; khi đó dòng thứ hai và dòng thứ ba đều chứa toàn bộ các vị trí từ ~1~ đến ~n~.

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

• Nhập ~n~ và dãy ~a~.
• Khởi tạo ~mn = mx = a[1]~.
• Duyệt từ phần tử thứ hai đến phần tử cuối, cập nhật giá trị nhỏ nhất và lớn nhất.
• In ~mn~ và ~mx~.
• Duyệt dãy từ trái sang phải, in các vị trí ~i~ mà ~a[i] = mn~.
• Duyệt thêm một lần, in các vị trí ~i~ mà ~a[i] = mx~.

3. Mô phỏng ví dụ

Dãy: 2 5 10 7 2 10 3 8 9 2.

• Giá trị nhỏ nhất: ~2~, xuất hiện tại các vị trí ~1, 5, 10~.
• Giá trị lớn nhất: ~10~, xuất hiện tại các vị trí ~3, 6~.

Do đó, kết quả gồm ba dòng như trong ví dụ.

4. Độ phức tạp

• Thời gian: ~O(n)~, vì chỉ duyệt dãy một số lần cố định.
• Bộ nhớ: ~O(n)~, để lưu dãy và xác định lại các vị trí sau khi tìm min/max.

5. Code C++ tham khảo

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

int n, a[100005], mn, mx;

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

    mn = mx = a[1];
    for (int i = 2; i <= n; i++) {
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }

    cout << mn << " " << mx << endl;

    bool first = true;
    for (int i = 1; i <= n; i++) {
        if (a[i] == mn) {
            if (!first) cout << " ";
            cout << i;
            first = false;
        }
    }
    cout << endl;

    first = true;
    for (int i = 1; i <= n; i++) {
        if (a[i] == mx) {
            if (!first) cout << " ";
            cout << i;
            first = false;
        }
    }
    cout << endl;
    return 0;
}

6. Những lỗi thường gặp

• Nhầm chỉ số mảng bắt đầu từ ~0~ với vị trí đề bài bắt đầu từ ~1~.
• Chỉ in vị trí đầu tiên của số nhỏ nhất hoặc lớn nhất, bỏ sót các lần xuất hiện khác.
• Khởi tạo ~mn = 0~ hoặc ~mx = 0~, dẫn đến sai khi dãy chỉ có số dương hoặc chỉ có số âm.
• Quên trường hợp ~n = 1~ hoặc mọi phần tử đều bằng nhau.