Giả sử chúng ta có một danh sách các số được gọi là nhật ký và một giới hạn giá trị khác. Mỗi phần tử trong nhật ký [i] đại diện cho kích thước của nhật ký được tạo bởi người dùng thứ i. Và giới hạn thể hiện tổng kích thước nhật ký mà chúng ta có thể lưu trữ trong cơ sở dữ liệu của mình. Chúng ta phải tìm x lớn nhất sao cho nếu chúng ta cắt ngắn mọi nhật ký trong nhật ký có kích thước tối đa là x và tổng các kích thước nhật ký bên trái là tối đa giới hạn. Nếu không cần cắt bớt nhật ký, thì chỉ cần trả về kích thước nhật ký lớn nhất.
Vì vậy, nếu đầu vào giống như nhật ký =[500, 200, 10000, 500, 4000] giới hạn =3000, thì đầu ra sẽ là 900, vì chúng ta cắt ngắn nhật ký thành 900, thì chúng ta có thể nhận được [500, 200, 900, 500 , 900] bây giờ tổng là 3000
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- lo:=0
- chào:=1 + tối đa nhật ký
- while lo + 1
- mi:=lo + tầng của (hi - lo) / 2
- nếu tổng của tất cả các phần tử có trong danh sách với (tối thiểu là mi và log cho mỗi bản ghi nhật ký) <=limit, thì
- lo:=mi
- nếu không,
- chào:=mi
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(logs, limit): lo, hi = 0, max(logs) + 1 while lo + 1 < hi: mi = lo + (hi - lo) // 2 if sum(min(mi, log) for log in logs) <= limit: lo = mi else: hi = mi return lo logs = [500, 200, 10000, 500, 4000] limit = 3000 print(solve(logs, limit))
Đầu vào
[500, 200, 10000, 500, 4000], 3000
Đầu ra
900