Chương trình tìm số phần tử tối thiểu cần thêm để đạt tổng mục tiêu trong Python

Cho danh sách nums, giới hạn k và mục tiêu t. Mỗi phép toán: chọn số e ∈ [-k, k] thêm vào cuối nums. Tìm số phép tối thiểu để tổng = t.

Ví dụ: , , → kết quả . Thêm [4,4,4,3] → tổng = 3+1+4+4+4+3 = 19.

Thuật toán giải quyết (O(1))

3. (số phép dùng giá trị tối đa k)
4. Nếu : (cần thêm 1 phép cho phần dư)
5. Trả về

Ví dụ minh họa

def solve(nums, k, t):
    total = sum(nums)
    diff = abs(t - total)
    result = diff // k
    if result * k != diff:
        result = result + 1
    return result

nums = [3, 1]
k = 4
t = 19
print(solve(nums, k, t))

Đầu vào

[3, 1], 4, 19

Đầu ra

4