USACO 2012 - Hay Bales
Xem PDFĐàn bò lại giở trò! Farmer John đã cẩn thận sắp xếp \(N\) đống kiện cỏ khô (\(1 \leq N \leq 10\,000\)), mỗi đống có cùng chiều cao. Tuy nhiên, khi ông không để ý, đàn bò chuyển một số kiện cỏ khô giữa các đống, khiến chiều cao của chúng không còn nhất thiết bằng nhau. Cho chiều cao mới của tất cả các đống, hãy giúp Farmer John xác định số kiện cỏ khô ít nhất mà ông cần di chuyển để khôi phục tất cả các đống về chiều cao ban đầu bằng nhau.
Dữ liệu vào
Dòng đầu tiên chứa số lượng đống \(N\) (\(1 \leq N \leq 10\,000\)).
Mỗi dòng trong \(N\) dòng tiếp theo chứa số kiện cỏ khô trong một đống, là một số nguyên trong khoảng \(1 \ldots 10\,000\).
Dữ liệu ra
In một số nguyên là số kiện cỏ khô ít nhất cần di chuyển để khôi phục các đống về cùng một chiều cao.
Ví dụ
Ví dụ 1
Input
4
2
10
7
1Output
7Giải thích
Có 4 đống với chiều cao lần lượt là 2, 10, 7 và 1.
Bằng cách di chuyển 7 kiện cỏ khô (3 kiện từ đống 2 sang đống 1, 2 kiện từ đống 2 sang đống 4 và 2 kiện từ đống 3 sang đống 4), ta có thể làm cho mọi đống đều có chiều cao 5.
Nguồn
USACO 2011 December Contest, Bronze Division — Hay Bales. Tác giả đề: Brian Dean, 2011.
Kỳ thi:
- USACO 2011 - Tháng 12 - Hạng Đồng (1 Tháng 12., 2011)
Bình luận