Ý Kiến Đa Số

Hướng tiếp cận

Câu hỏi cốt lõi: với một loại cỏ $v$ cố định, khi nào ta có thể "lan" $v$ ra cả đàn?

Quan sát đầu tiên: nếu trong dãy đã tồn tại một đoạn liên tiếp gồm $\ge 2$ con bò cùng thích $v$, thì ta luôn lan được. Thật vậy, giả sử $h_i=h_{i+1}=v$. Lấy nhóm $\{i-1,i,i+1\}$: trong nhóm này $v$ chiếm $2/3>1/2$, nên cả ba con đều chuyển sang $v$. Cứ thế mở rộng sang trái và sang phải, mỗi bước thêm một con bò, đến khi phủ toàn bộ dãy.

Vậy đủ để tìm xem có thể tạo ra một cặp liên tiếp cùng giá trị $v$ hay không.

Nhận xét quan trọng

Loại $v$ hợp lệ khi và chỉ khi tồn tại $i$ sao cho $h_i=h_{i+1}=v$ hoặc $h_i=h_{i+2}=v$.

Chiều thuận (đủ).

• Trường hợp $h_i=h_{i+1}=v$: đã có cặp liên tiếp, áp dụng quan sát trên.
• Trường hợp $h_i=h_{i+2}=v$ (với $h_{i+1}$ tùy ý): nhóm $\{i,i+1,i+2\}$ có hai con thích $v$ trên tổng ba con, chiếm đa số. Một thao tác duy nhất biến nhóm này thành ba con cùng thích $v$, tạo ra cặp liên tiếp $\Rightarrow$ quay về trường hợp trên.

Chiều ngược (cần). Giả sử không tồn tại $i$ nào để $h_i=h_{i+1}=v$ hay $h_i=h_{i+2}=v$. Khi đó hai vị trí bất kỳ thích $v$ cách nhau tối thiểu 3. Xét bất kỳ đoạn liên tiếp độ dài $L$: số con thích $v$ trong đoạn không vượt quá $\lceil L/3\rceil$, luôn $\le L/2$ (với $L\ge 2$). Vậy $v$ không bao giờ là đa số tuyệt đối trong bất kỳ nhóm nào, không có thao tác nào sinh thêm con thích $v$, và không thể tạo ra hai con thích $v$ liên tiếp. Số con thích $v$ chỉ có thể giảm hoặc giữ nguyên qua các thao tác, nên không thể phủ kín đàn.

Thuật toán

1. Đọc dãy $h_1,\dots ,h_n$.
2. Khởi tạo tập $S=\varnothing$.
3. Với $i=1,\dots ,n-1$: nếu $h_i=h_{i+1}$, thêm $h_i$ vào $S$.
4. Với $i=1,\dots ,n-2$: nếu $h_i=h_{i+2}$, thêm $h_i$ vào $S$.
5. Nếu $S$ rỗng in -1; ngược lại in các phần tử của $S$ theo thứ tự tăng dần.

Lưu ý cài đặt: dùng set (đảm bảo sắp xếp và loại trùng) hoặc mảng đánh dấu kết hợp duyệt theo thứ tự giá trị. Tránh dùng map<int,int> đếm tần suất rồi so với $n/2$ — đó là tư duy "đa số toàn mảng", không đúng với bài này.

Độ phức tạp

• Thời gian: $O(N\log N)$ nếu dùng set, $O(N)$ nếu dùng mảng đánh dấu.
• Bộ nhớ: $O(N)$.