HSG THPT Thanh Hóa 2021 - Mua Quà
View as PDF
Nhân dịp chào đón Giáng sinh, Thành quyết định lấy hết tiền học bổng của mình để mua toàn bộ ~N~ món quà lưu niệm tặng các bạn nữ trong lớp, các món quà được đánh số từ ~1~ đến ~N~, món thứ ~i~ có giá là ~a_i~, ~i = 1 \div N~. Cảm động trước hành động của Thành, chủ cửa hàng đã có chương trình khuyến mãi đặc biệt dành cho em. Thành được phép chia ~N~ món quà thành một hay nhiều đơn hàng với điều kiện hai món quà bất kì trong một đơn phải có giá chênh lệch nhau không bé hơn ~K~. Với mỗi đơn hàng như vậy, Thành chỉ phải thanh toán số tiền là giá của món quà đắt nhất trong đơn đó mà thôi.
Yêu cầu: Giúp Thành chia ~N~ món quà thành các đơn hàng sao cho tổng số tiền phải trả cho tất cả đơn hàng là nhỏ nhất.
Input
Vào từ tệp văn bản BAI3.INP gồm ~2~ dòng:
Dòng thứ nhất chứa hai số nguyên dương ~N~ và ~K~ (~N \le 10^5, K \le 10^9~)
Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2,.. a_N~ (~a_i \le 10^9, i = 1 \div N~)
Output
Ghi ra tệp văn bản BAI3.OUT một số nguyên duy nhất là tổng số tiền phải trả.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~50~ | ~N \le 10^4~ |
| 2 | ~50~ | Không ràng buộc gì thêm |
Sample Input 1
3 2
1 3 3
Sample Output 1
6
Comments
cái sample bị sao vậy ạ hay mình hiểu sai. giá là 1 3 3 thì gộp nó thành một đơn thì chỉ cần trả là 3 mà nhỉ, sao lại kết quả sample là 6
mn cho e xin code bài này vs đc k ạ
Ai có test case cho bài này ko ạ cho mình xin ạ ^^
ai gải thích giúp mình cái input output với đọc đề vẫn chưa hiểu lắm-,-
ủa tui sao output ra 3 v mn?
Sai á anh hihi
Làm ơn đi
Hửm.Chúng ta có cùng cảnh ngộ
Cái này là đã có cùng cảnh ngộ nha:)))
Soi kỹ thế bạn
Làm ơn giúp mình đi mà please
Vậy bạn đã hiểu chưa
Có lẽ là sơ sơ
Vậy help đi tui đọc hướng dẫn ko hiểu
Bạn làm được sub 1 chưa
Chưa kể mình còn ko biết cách lặp trâu nữa
Ca này chịu thua
Chưa Do ko hiểu đề
Có ai giải thích thuật toán giúp ko Tui đọc hướng dẫn ko hiểu Cho tui cảm ơn trước nha