Nhà máy chế biến kim loại
Đề bài
Mô tả
Yulia làm việc tại một nhà máy chế biến kim loại ở Ekaterinburg. Nhà máy này chế biến quặng khai thác từ dãy núi Ural, tách ra các kim loại quý như chalcopyrit, bạch kim và vàng từ quặng.
Mỗi tháng nhà máy nhận lô quặng thô. Yulia cần chia các lô này thành hai nhóm dựa trên mức độ giống nhau của chúng. Sau đó, mỗi nhóm được gửi tới một trong hai phân xưởng chế biến quặng của nhà máy.
Để chia nhóm, trước hết Yulia tính một khoảng cách cho mỗi cặp lô và , khoảng cách càng nhỏ thì hai lô và càng giống nhau. Với một tập con các lô, cô định nghĩa độ chênh lệch của là khoảng cách lớn nhất giữa hai lô trong tập con đó, tức là
Sau đó Yulia chia các lô thành hai tập con và sao cho tổng độ chênh lệch là nhỏ nhất. Nhiệm vụ của bạn là giúp cô tìm cách chia này.
Dữ liệu vào
Dữ liệu gồm một bộ test duy nhất. Dòng đầu tiên chứa số nguyên , số lô quặng. dòng tiếp theo chứa các khoảng cách . Dòng thứ trong số đó chứa số nguyên, số nguyên thứ của dòng là giá trị . Các khoảng cách đối xứng, tức là , và khoảng cách từ một lô tới chính nó bằng .
Dữ liệu ra
In ra tổng độ chênh lệch nhỏ nhất có thể khi chia các lô thành hai nhóm.
Ràng buộc
- .
- Mọi khoảng cách là số nguyên trong đoạn .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 4 5 0 2 1 3 7 2 0 4 |
4 | Chọn và : và , tổng . |
| 7 1 10 5 5 5 5 5 10 5 5 5 100 100 5 5 10 5 5 98 99 3 |
15 | Chọn và : và , tổng . |
Bình luận