Mã bài:
present
Điểm:
1,2 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Tèo đang ở siêu thị Big D và mua quà cho bạn gái mình. Tèo rất giàu nên đã mua ~n~ món quà với kích thước to nhỏ khác nhau. Tuy nhiên, siêu thị không có sẵn hộp quà cho tất cả các món quà, vì thế Tèo phải gọi trợ lí của mình là Tí để ship đúng ~n~ hộp quà đến siêu thị. Hộp quà thứ ~i~ Tèo yêu cầu to ~a_i~ đơn vị. Chẳng may thay xe của Tí rất nhỏ nên phải lồng các hộp quà vào nhau để tối ưu không gian.
Hộp quà thứ ~i~ có thể được đặt trong hộp quà ~j~ khi:
- Hộp quà ~j~ lớn hơn hộp quà ~i~ ~(a_i < a_j)~.
- Hộp quà ~i~ chưa được đặt bên trong một hộp quà nào
- Hộp quà ~j~ chưa chứa hộp quà nào.
Hãy tìm số hộp quà cuối cùng sau khi lồng để tối ưu không gian nhất.
Dữ liệu vào
- Gồm ~2~ dòng:
- Dòng đầu tiên chứa số nguyên dương ~n(n\le 2\cdot 10^5)~ .
- Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,\dots,a_n (a_i \le 10^ 9,1\le i\le n)~.
Kết quả ra
- Một dòng là kết quả bài toán
Ràng buộc
- Có ~20 \%~ test tương ứng với ~20\%~ số điểm có ~n\le 10~
- Có ~20 \%~ test tương ứng với ~20\%~ số điểm có ~n\le 1000~
- ~60 \%~ test còn lại với tương ứng ~60\%~ số điểm không có ràng buộc gì hơn.
Ví dụ
Dữ liệu
3
4 5 6
Kết quả
1
Giải thích
- Bỏ hộp quà ~4~ vào ~5~, bỏ hộp qùa ~5~ vào ~6~. Khi nãy chỉ còn ~1~ hộp quà ~6~.
Dữ liệu
4
6 4 6 5
Kết quả
2
Giải thích
- Bỏ hộp quà ~4~ vào ~6~, bỏ hộp qùa ~5~ vào ~6~. Khi nãy còn ~2~ hộp quà ~6~.
Bình luận