Hướng dẫn giải của THT TQ 2023 - Bảng B & C2 - Bài 2, 1
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 làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Subtask 1, 2
- Ta duyệt những điểm ~x~ có nhiều hơn ~n~ hình nhữ nhật phủ lên
- Với mỗi điểm ~x~ ta tính toán điểm ~y~ nhỏ nhất sau cho ~(x, y)~ nằm trong ít nhất ~n~ hình chữ nhật
- Duy trì 1 biến pair<int, int> để tránh trường hợp xấu nhất
Subtask 3
- Ta nhận thấy đáp án tối ưu nhất chỉ cần ~n~ hình chữ nhật
- Ta thử ~n~ hình chữ nhật bất kì sau đó lấy kết quả tốt nhất, nếu không có in ra ~-1~
- Vậy ta phải thử ~n+1~ lần
Đô phức tạp ~\mathcal O(N^{2})~
Subtask 4
- Tương tự như Subtask 1, 2 chỉ cần nén mảng
Bình luận