Kệ sách hoàn chỉnh
Đề bài
Mô tả
Thư viện Hogwarts có cuốn sách xếp thành một hàng dài. Mỗi cuốn sách thuộc một thể loại nào đó, được đánh số bằng số nguyên dương. Biểu tượng của thể loại được ghi trên gáy mỗi cuốn sách.
Madam Pince, thủ thư của Hogwarts, muốn chọn một đoạn sách liên tiếp để trưng bày trên một kệ sách đặc biệt. Kệ sách được gọi là "hoàn chỉnh" nếu nó chứa ít nhất một cuốn sách từ mọi thể loại có trong thư viện.
Cho dãy số nguyên đại diện cho thể loại của từng cuốn sách theo thứ tự trên hàng. Hãy tìm độ dài ngắn nhất của một đoạn liên tiếp sao cho đoạn đó chứa đủ tất cả các thể loại phân biệt có trong dãy.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên — số lượng sách.
- Dòng thứ hai chứa số nguyên — thể loại của mỗi cuốn sách.
Dữ liệu ra
- In ra một số nguyên duy nhất — độ dài ngắn nhất của đoạn liên tiếp chứa đủ tất cả các thể loại.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 1 2 1 3 2 1 |
3 | Có 3 thể loại phân biệt: 1, 2, 3. Đoạn ngắn nhất chứa đủ cả 3 thể loại là [2, 1, 3] (vị trí 2 đến 4) hoặc [1, 3, 2] (vị trí 3 đến 5), đều có độ dài 3. |
| 5 4 4 4 4 4 |
1 | Chỉ có 1 thể loại duy nhất (thể loại 4), nên bất kỳ cuốn sách đơn lẻ nào cũng đủ tạo thành kệ sách hoàn chỉnh. Độ dài ngắn nhất là 1. |
Ghi chú
- Đoạn liên tiếp có độ dài .
- Bài toán đảm bảo luôn tồn tại ít nhất một đoạn hoàn chỉnh (toàn bộ dãy là một đoạn hợp lệ).
https://oj.chuyentin.pro/problem/bookshelf
Bình luận