Chương trình đếm số review 5 sao cần thêm để đạt ngưỡng phần trăm trong Python

Cho danh sách reviews (mỗi phần tử [x, y]: x sao 5, y tổng review) và ngưỡng t%. Tìm số review 5 sao thêm tối thiểu để tỷ lệ ≥ t%.

Ví dụ: , → kết quả . Tổng: 8 sao 5 / 12 review. Cần 7 review 5 sao nữa để đạt 78%.

Thuật toán giải quyết (Công thức toán học O(n))

1. Tính tổng (sao 5), (tổng review)
2. Nếu = t*b: trả về 0
3. (thiếu bao nhiêu "điểm phần trăm")
4. Mỗi review 5 sao thêm tăng tỷ số: → cần giải bất phương trình
5. Kết quả:

Ví dụ minh họa

def solve(reviews, t):
    a = 0
    b = 0
    for c, d in reviews:
        a += c
        b += d
    if a * 100 >= t * b:
        return 0
    delta = t * b - 100 * a
    return (delta + (99 - t)) // (100 - t)

reviews = [[3, 4], [1, 2], [4, 6]]
t = 78
print(solve(reviews, t))

Đầu vào

[[3, 4], [1, 2],[4, 6] ],78

Đầu ra

7