Hướng dẫn giải của [TS10 Nam Định 2025 - 2026] Cắt dây
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.
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ưởng
Lưu số lượng đoạn theo độ dài bằng một bảng đếm sắp theo độ dài giảm dần. Mỗi bước lấy nhóm đoạn dài nhất. Nếu còn ít lượt cắt hơn số đoạn trong nhóm này, độ dài lớn nhất vẫn là độ dài hiện tại và số lượng giảm tương ứng. Ngược lại cắt toàn bộ nhóm và cộng số lượng vào hai độ dài con sinh ra.
Độ phức tạp
~O(\log n)~ nhóm độ dài.
Bình luận