Không gian hoán đổi
Đề bài
Mô tả
Bạn quản trị một cụm máy tính lớn, các ổ cứng của cụm dùng nhiều loại hệ thống tệp khác nhau để lưu dữ liệu. Gần đây bạn quyết định thống nhất tất cả về cùng một loại hệ thống tệp. Đây là một thử thách không nhỏ vì mọi ổ đều đang được sử dụng, ổ nào cũng chứa đầy dữ liệu quan trọng tới đúng dung lượng của nó, và bạn không được phép làm mất bất kỳ dữ liệu nào. Hơn nữa, định dạng lại một ổ sang hệ thống tệp mới có thể làm dung lượng của ổ thay đổi đáng kể. Để việc định dạng lại khả thi, bạn sẽ phải mua thêm một ổ cứng phụ. Dĩ nhiên bạn muốn tiết kiệm tiền bằng cách làm cho dung lượng của ổ phụ này nhỏ nhất có thể.
Bạn có thể định dạng lại các ổ theo thứ tự bất kỳ. Trước khi định dạng lại một ổ, bạn phải chuyển toàn bộ dữ liệu trên ổ đó sang một hoặc nhiều ổ khác, được phép chia nhỏ dữ liệu nếu cần. Sau khi một ổ được định dạng lại, bạn có thể dùng nó ngay để chứa dữ liệu từ các ổ khác. Dữ liệu không nhất thiết phải nằm lại trên đúng các ổ ban đầu của nó (thực tế điều này thậm chí có thể không làm được nếu một số ổ có dung lượng nhỏ hơn với hệ thống tệp mới). Cũng được phép để một phần dữ liệu nằm lại trên ổ phụ khi kết thúc.
Ví dụ, giả sử có bốn ổ A, B, C, D với dung lượng lần lượt , , , GB. Với hệ thống tệp mới, dung lượng của chúng lần lượt trở thành , , , GB. Nếu chỉ mua thêm GB, bạn có thể chuyển dữ liệu trên ổ B sang đó rồi định dạng lại ổ B. Lúc này ổ B trống GB, nên bạn có thể chuyển GB của ổ A sang ổ B rồi định dạng lại ổ A. Cuối cùng, bạn chuyển tổng cộng GB dữ liệu của ổ C và ổ D sang ổ A, rồi định dạng lại C và D.
Dữ liệu vào
Dòng đầu chứa số nguyên , số ổ cứng trong cụm. Mỗi dòng trong dòng tiếp theo mô tả một ổ bằng hai số nguyên và , trong đó là dung lượng với hệ thống tệp cũ và là dung lượng với hệ thống tệp mới.
Mọi dung lượng tính bằng gigabyte.
Dữ liệu ra
In ra tổng dung lượng phụ (tính bằng gigabyte) nhỏ nhất bạn phải mua để định dạng lại được tất cả các ổ.
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 6 6 1 7 3 5 3 5 |
1 | Đây là ví dụ trong đề: mua GB, định dạng lại lần lượt B, A, rồi C và D. Không mua gì thì không thể chuyển dữ liệu của ổ nào ra ngoài. |
| 4 2 2 3 3 5 1 5 10 |
5 | Mua GB: chuyển dữ liệu ổ thứ tư sang ổ phụ và định dạng lại nó (còn trống GB), sau đó lần lượt định dạng lại ổ thứ nhất, thứ hai, rồi ổ thứ ba (lúc đó còn trống GB trên các ổ khác, đủ chứa GB). Ổ thứ nhất và thứ hai không đổi dung lượng, nên trước lần đầu định dạng lại ổ thứ ba hoặc thứ tư, chỗ trống đúng bằng dung lượng mua thêm, mà cả hai ổ này đều chứa GB: ít hơn GB là không đủ. |
Bình luận