#5223. LOADBALANCE - Cân bằng tải trên nhiều máy chủ

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

N máy chủ, máy chủ thứ i a_i công việc cần xử lý. Bạn muốn di chuyển các công việc sao cho số lượng công việc trên mỗi máy chủ là cân bằng nhất có thể. Bạn được phép di chuyển công việc giữa các máy chủ. Tìm số lượng công việc ít nhất cần phải di chuyển.

Dữ liệu:

  • Dòng đầu tiên chứa số nguyên N ( 1 \le N \le 10^5 ).
  • Dòng thứ hai chứa N số nguyên a_i ( 1 \le a_i \le 10^9 ).

Kết quả: In ra số lượng công việc ít nhất cần phải di chuyển.

Ví dụ:

Dữ liệu:

3
10 20 30

Kết quả:

10

Giới hạn:

  • 1 \le N \le 10^5
  • 1 \le a_i \le 10^9