(Tham khảo bài Post Đề đề xuất DHBB 2017 của THPT CHUYÊN NGUYỄN TẤT THÀNH – YÊN BÁI)
Trên quốc lộ mà ta coi như một trục tọa độ có hộ dân cư sinh sống tại các điểm có tọa độ là các số nguyên phân biệt (theo thứ tự tăng dần). Công ty cấp nước muốn lắp trạm cấp nước cho dân cư nơi đây, sau khi lắp các trạm cấp nước, công ty cấp nước sẽ kéo đường ống về cho tất cả các hộ dân cư sử dụng, hộ dân cư nào ở gần trạm cấp nước nào nhất sẽ được kéo đường ống từ trạm cấp nước đó. Bạn được giao nhiệm vụ tìm vị trí đặt trạm cấp nước thỏa mãn các điều kiện sau:
Các điểm đặt các trạm cấp nước là phân biệt.
Mỗi trạm cấp nước được đặt trùng với tọa độ của một hộ dân cư nào đó (để tiện việc bảo vệ, trông coi).
Tổng độ dài đường ống để kéo từ các trạm cấp nước về các hộ dân cư là nhỏ nhất (giả sử tọa độ một trạm cấp nước là , tọa độ của một hộ dân cư là thì độ dài đường ống cần kéo từ trạm cấp nước tới hộ dân cư đang xét là ).
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương và được ghi cách nhau một dấu cách.
Dòng thứ hai chứa số nguyên là tọa độ các hộ dân cư, hai số liên tiếp được ghi cách nhau một dấu cách.
Dữ liệu ra:
Dòng đầu chứa tổng độ dài đường ống cần sử dụng.
Dòng thứ hai chứa số nguyên theo thứ tự tăng dần là tọa độ lắp đặt các trạm cấp nước, hai số liên tiếp được ghi cách nhau một dấu cách. Nếu có nhiều phương án lắp đặt, hãy đưa ra phương án bất kỳ.
Ví dụ:
Dữ liệu vào:
4 2
1 2 3 5
Dữ liệu ra:
2
2 5
Giải thích:
Với cách lắp trạm cấp nước như trên thì các hộ dân cư thứ sẽ được lấy nước từ trạm số (có tọa độ là ), hộ dân cư thứ sẽ lấy nước từ trạm số (có tọa độ là ). Tổng đường ống cần dùng là .
