trang chủ / đề bài / bookshelf

Kệ sách hoàn chỉnh

Đề bài

Mô tả

Thư viện Hogwarts có N 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 N số nguyên a1,a2,…,aN đạ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 N — số lượng sách.
  • Dòng thứ hai chứa N số nguyên a1,a2,…,aN — 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

  • 1≤N≤2×105
  • 1≤ai≤N

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 [al,al+1,…,ar] có độ dài r−l+1.
  • 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ệ).

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0