Cho danh sách logs (kích thước log của từng user) và limit (dung lượng tối đa). Tìm giá trị x lớn nhất sao cho nếu cắt tất cả log > x về x, tổng dung lượng ≤ limit. Nếu không cần cắt, trả về log lớn nhất.
Ví dụ
Input: logs = [500, 200, 10000, 500, 4000], limit = 3000
Output: 900
Giải thích: Cắt về 900 → [500, 200, 900, 500, 900], tổng = 3000.
Thuật toán: Tìm kiếm nhị phân (Binary Search)
Hàm f(x) = sum(min(x, log) for log in logs) là hàm đơn điệu không giảm theo x. Tìm x lớn nhất sao cho f(x) ≤ limit.
lo = 0,hi = max(logs) + 1- While
lo + 1 < hi:mi = lo + (hi - lo) // 2- Nếu
f(mi) ≤ limit:lo = mi - Ngược lại:
hi = mi
- Trả về
lo
Mã Python
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
# Test
logs = [500, 200, 10000, 500, 4000]
limit = 3000
print(solve(logs, limit)) # Output: 900Phân tích độ phức tạp
- Thời gian: O(n log M) - n = len(logs), M = max(logs)
- Không gian: O(1)
Ứng dụng: Bài toán phân bổ tài nguyên, rate limiting, dung lượng lưu trữ với ngưỡng.