Hướng dẫn giải của Đội Hình Tốt Nhất
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ác giả:
Lời giải: Đội Hình Tốt Nhất
Hướng tiếp cận
Xây dựng hàng bằng cách chọn các suffix maximum, sau đó tìm vị trí tối ưu để di chuyển một phần tử cải thiện thứ tự từ điển.
Thuật toán
- Xây dựng ban đầu: duyệt từ phải sang trái, lấy các suffix maximum.
- Tìm vị trí cải thiện: thử di chuyển phần tử để tạo suffix maximum mới lớn hơn.
- Chọn vị trí cải thiện đầu tiên (sớm nhất).
Độ phức tạp
- Thời gian: amortized mỗi test case
Bình luận