Chương trình tìm số khách hàng hài lòng tối đa Python

Cho mảng customers (số khách mỗi phút), mood (1: vui, 0: buồn), và số k. Có thể chọn một đoạn dài k trong mood biến tất cả thành 1. Tìm tối đa số khách vui lòng.

Ví dụ: customers=[2,3,6,6,3], mood=[1,1,0,0,0], k=2 → 17 (biến mood[2], mood[3] thành 1).

Giải thuật (Prefix sum + Cửa sổ trượt)

1. Tính s = tổng khách đã vui (mood=1)
2. Mảng a[i+1] = tổng khách buồn (mood=0) từ đầu đến i
3. Tìm cửa sổ độ dài k có tổng a[i] - a[i-k] lớn nhất
4. Kết quả = s + max_window_sum

Ví dụ triển khai

def solve(customers, mood, k):
    n = len(mood)
    a = [0] * (n + 1)
    s = 0
    for i in range(n):
        a[i+1] = a[i]
        if mood[i]:
            s += customers[i]
        else:
            a[i+1] += customers[i]
    d = 0
    for i in range(k, n+1):
        d = max(d, a[i] - a[i-k])
    return s + d

print(solve([2,3,6,6,3], [1,1,0,0,0], 2))

Đầu vào

[2, 3, 6, 6, 3], [1, 1, 0, 0, 0], 2

Đầu ra

17