trang chủ / bài tập / clash26 / lời giải

Clash!

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả:

huunguyen

Lời giải: Clash!

Hướng tiếp cận

Biểu diễn mỗi lá bài bằng cặp $(- isWin, cost)$ . Bác John luôn chơi lá có cặp nhỏ nhất theo thứ tự từ điển (ưu tiên điều kiện thắng, sau đó ưu tiên chi phí thấp).

Thuật toán

Mô phỏng: Dùng priority queue (min-heap). Đưa $H - 1$ lá đầu vào heap. Lặp $N - H + 1$ lần: thêm lá tiếp theo, lấy lá nhỏ nhất ra chơi. Ghi nhận thời gian tích lũy và vị trí các điều kiện thắng.
Trả lời truy vấn: Với thời gian $t$ :
- Số chu kỳ đầy đủ: $t \div cycle\_len$
- Phần dư: tìm nhị phân số lá chơi thêm trong phần dư
- Tổng điều kiện thắng = chu kỳ đầy $\times$ wins/chu kỳ + wins trong phần dư

Độ phức tạp

Thời gian: $O (N \log N + Q \log N)$
Bộ nhớ: $O (N)$

Bình luận

Không có bình luận tại thời điểm này.