Búp bê
Xem PDFCông ty đồ chơi X nhập khẩu n con búp bê gỗ. Các con búp bê được đánh số từ 1 tới n trong đó con búp bê thứ i là một hộp rỗng có kích thước là một số nguyên ai. Người ta có thể lồng con búp bê thứ i vào trong con búp bê thứ j nếu con búp bê thứ j đang rỗng và \(a_i+k ≤ a_j\), với k là một số nguyên dương cho trước. Bằng cách lồng các con búp bê vào nhau theo cách như vậy, công ty X chỉ cần tìm chỗ đặt những con búp bê ngoài cùng (những con búp bê không nằm trong bất kỳ con búp bê nào khác) vào kho.
Yêu cầu: Hãy giúp công ty X lồng các con búp bê vào nhau sao cho tổng kích thước các con búp bê ngoài cùng là nhỏ nhất.
Input
Gồm 2 dòng
-
Dòng 1 chứa hai số nguyên dương \(n ≤ 10^5\); \(k ≤ 10^9\) cách nhau một khoảng trắng.
-
Dòng 2 chứa n số nguyên dương \(a_1, a_2, ..., a_n\) ( \(a_i ≤ 10^9\)), mỗi số cách nhau một khoảng trắng.
Output
- Là một số nguyên duy nhất là tổng kích thước các con búp bê ngoài cùng theo phương án tìm được.
Example
Test 1
Input
8 2
8 4 2 1 1 3 5 9Output
18
Bình luận
Là sao vậy mình vẫn chưa hiểu. Tìm con tổng kích thước các con búp bê ngoài cùng là nhỏ nhất là sao? Sao nhập:
8 2
8 4 2 1 1 3 5 9
lại ra 18
tôi là khải tồ nè
hí
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.