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

    solution

    Đề bài: [Giải thuật] Phần tử đa số vượt một phần ba (Boyer-Moore mở rộng)

    Cho dãy a0,…,an−1a_0,\dots,a_{n-1}a0​,…,an−1​. Tìm tất cả các giá trị xuất hiện nhiều hơn n/3n/3n/3 lần (nhiều nhất có hai giá trị như vậy). In chúng theo thứ tự tăng dần, cách nhau bởi dấu cách; nếu không có, in NONE.

    Dùng biến thể thuật toán bỏ phiếu Boyer-Moore với hai ứng viên.

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

      Dòng đầu: nnn. Dòng hai: nnn số aia_iai​.

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

      1≤n≤1061 \le n \le 10^61≤n≤106, ∣ai∣≤109|a_i| \le 10^9∣ai​∣≤109.

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

      Các giá trị thỏa mãn (tăng dần) trên một dòng, hoặc NONE.

    Ví dụ:

    Đầu vào:

    7
1 1 1 2 2 3 2

    Đầu ra:

    1 2

    Giải thích:

    n=7, ngưỡng n/3≈2.33. Số 1 xuất hiện 3 lần, số 2 xuất hiện 3 lần (đều >2.33), số 3 chỉ 1 lần. In 1 2.

    Đang tải editor...