BOCHANG - Bốc hàng
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
0.1s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Có N kho hàng, các kho hàng chứa các thùng hàng cùng loại. Chủ các kho hàng này muốn chuyển tất cả các thùng hàng về một kho nào đó trong N kho nói trên, vì vậy ông ta khoán công việc này cho một nhóm công nhân bốc vác. Khi hợp đồng, các công nhân và ông chủ kho hàng thống nhất công để chuyển một kho hàng này về kho kia là một thùng hàng.
Yêu cầu: Giúp ông chủ xác định số thùng hàng ít nhất dùng để trả công cho nhóm công nhân để chuyển tất cả các thùng hàng về một kho?
Input
-Dòng đầu ghi số N là số kho hàng.(~ 1 \le N \le 10^5 ~)
-Dòng thứ hai ghi N số nguyên dương , trong đó ai là số thùng hàng có trong kho thứ i (1 ≤ i ≤ N).(~ 1 \le a_i \le 10^3 ~)
Output
Gồm một số là số thùng hàng dùng để trả công
Sample
Input #1
5
6 16 3 5 5
Output #1
3
Problem source: Thcs Lập Thạch
Bình luận
Ý tưởng: Sắp xếp lại kho hàng theo thứ tự tăng dần về mặt hàng. Trong ví dụ trên sẽ là: 3 5 5 6 16.
Ta sẽ thực hiện chuyển các kho hàng có nhiều hàng nhất vào nhau và trừ đi số hàng trong kho hàng đầu tiên (ít nhất). Minh hoạ:
Chưa chuyển: 3, 5, 5, 6, 16
16 chuyển vào 6, kho hàng đầu -1: 2, 5, 5, 22
22 chuyển vào 5, kho hàng đầu -1: 1, 5, 27
27 chuyển vào 5, kho hàng đầu -1: 0, 32
Kho đầu tiên = 0 thì không cần chuyển nữa mà chỉ còn lại kho có 32 mặt hàng
Kho đầu về 0 vậy ta chỉ cần 3 bước chuyển và mất 3 thùng hàng là từ 5 kho về 1 kho. Tương tự nếu kho đầu tiên mà hết hàng (= 0) trong khi vẫn chưa chuyển hết hàng thì ta dịch lên kho thứ 2 rồi lại trừ đến khi kho 2 về 0,...