Công suất thấp
Đề bài
Mô tả
Bạn đang chế tạo những con chip tiên tiến cho các cỗ máy. Làm chip thì dễ, nhưng nguồn điện lại là vấn đề, vì các viên pin hiện có có công suất khác nhau.
Xét bài toán với cỗ máy, mỗi máy có hai con chip, và mỗi con chip được cấp điện bởi viên pin. Điều bất ngờ là mỗi chip nhận được bao nhiêu điện không quan trọng, nhưng một cỗ máy hoạt động tốt nhất khi công suất của hai con chip của nó càng gần nhau càng tốt. Công suất của một con chip đơn giản là công suất nhỏ nhất trong viên pin của nó.
Bạn có một kho gồm viên pin và muốn phân chúng cho các con chip (mỗi viên pin dùng cho đúng một chip). Có thể không phân được sao cho trong mọi máy hai con chip có công suất bằng nhau, nhưng bạn muốn phân sao cho các chênh lệch càng nhỏ càng tốt. Chính xác hơn, bạn muốn nói với khách hàng rằng trong mọi cỗ máy, chênh lệch công suất giữa hai con chip không vượt quá , và bạn muốn nhỏ nhất có thể.
Để làm được điều này, bạn phải tìm một cách phân pin tối ưu cho các cỗ máy.
Xét ví dụ thứ nhất. Có cỗ máy, mỗi chip cần viên pin, và kho có các viên pin với công suất . Chẳng hạn, có thể gán các viên pin công suất cho một con chip, các viên cho con chip còn lại của cùng máy đó, các viên cho con chip thứ ba và các viên cho con chip thứ tư. Công suất của các con chip lần lượt là và , và chênh lệch công suất trong cả hai máy đều là . Lưu ý còn nhiều cách khác đạt được kết quả này.
Dữ liệu vào
Dữ liệu gồm một test duy nhất, trên hai dòng:
- Dòng đầu chứa hai số nguyên dương và : số cỗ máy và số viên pin của mỗi con chip.
- Dòng thứ hai chứa số nguyên : công suất của các viên pin.
Dữ liệu ra
In ra số nhỏ nhất sao cho có thể phân pin để trong mọi cỗ máy, chênh lệch công suất giữa hai con chip không vượt quá .
Ràng buộc
- , , .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 1 2 3 4 5 6 7 8 9 10 11 12 |
1 | Cách phân như trong đề: các chip , ở máy thứ nhất (công suất và ), , ở máy thứ hai (công suất và ). Không thể đạt vì mọi công suất đều khác nhau. |
| 2 2 3 1 3 3 3 3 3 3 |
2 | Chip chứa viên pin công suất có công suất , mọi chip khác có công suất , nên máy chứa chip đó có chênh lệch . |
Bình luận