Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [C++] Nth_element tìm trung vị

    Cho dãy N số nguyên (N lẻ). Dùng std::nth_element để tìm trung vị (phần tử thứ N/2 sau khi sắp tăng) trong thời gian trung bình O(N).

    • Định dạng đầu vào:

      Dòng 1: N (1 ≤ N ≤ 10^6, N lẻ). Dòng 2: N số nguyên.

    • Ràng buộc đầu vào:

      |a_i| ≤ 10^9. Không được dùng sort() trên toàn dãy (yêu cầu O(N) trung bình).

    • Định dạng đầu ra:

      Một số nguyên — trung vị.

    Ví dụ:

    Đầu vào:

    5
3 1 4 1 5

    Đầu ra:

    3

    Giải thích:

    Sắp tăng: 1 1 3 4 5; trung vị (vị trí 2) = 3.

    Đang tải editor...