Một công ty bán máy tính tổ chức bảo dưỡng máy tính miễn phí cho khách hàng trong n ngày. Ngày thứ i (1 ≤ i ≤ n) có ai khách hàng đăng ký nhưng công ty chỉ có thể thực hiện bảo dưỡng máy tính cho không quá bị khách hàng, Vì thế có một số khách hàng đã đăng ký trong ngày thứ i phải chuyển sang các ngày thứ j (1 ≤ j ≤ n). Ký hiệu d = max {|i-j|, 1≤i,j ≤ n}, trong đó i là ngày khách hàng đã đăng ký và j là ngày khách hàng được bảo dưỡng máy tính.
Yêu cầu: Tìm một phương án để mỗi ngày thứ i (1 ≤ i ≤ n) công ty thực hiện bảo dưỡng máy tính cho không quá b; khách hàng và sau n ngày tất cả khách hàng đã đăng ký đều được bảo dưỡng máy tính miễn phí sao cho giá trị d là nhỏ nhất.
Dữ liệu: Nhập vào từ bàn phím:
Dòng đầu chứa số nguyên dương n, với 2 ≤ n ≤ 10^5;
Dòng thứ hai chứa n số nguyên dương a1, a2, ..., an, mỗi số không vượt quá 10^9.
Dòng thứ ba chứa n số nguyên dương bị, b2, .., bn, mỗi số không vượt quá 10^9.
Kết quả: In ra giá trị d nhỏ nhất tìm được. Nếu không có phương án thỏa mãn các yêu cầu thì ghi ra giá trị -1.
Ví dụ:
Input:
4
6 14 50 1
50 3 16 5
Output:
2
Giải thích: Có thể chuyển 11 khách hàng từ ngày 2 sang ngày 1, 30 khách hàng từ ngày 3 sang ngày 1 và 4 khách hàng từ ngày 3 sang ngày 4.
Bình luận