Giả sử chúng ta có một danh sách khách hàng và một danh sách tâm trạng khác, hai danh sách này có cùng độ dài, chúng ta cũng có một số nguyên k khác. Bây giờ vào mỗi phút thứ i, khách hàng [i] số người đến cửa hàng và khi tâm trạng [i] =1, nó cho biết khách hàng đang vui và khi tâm trạng [i] =0, thì họ buồn. Chúng ta có thể đặt một danh sách phụ có kích thước k tâm trạng thành 1s, cuối cùng chúng ta phải tìm ra số người tối đa mà chúng ta có thể làm cho hạnh phúc.
Vì vậy, nếu đầu vào là khách hàng =[2, 3, 6, 6, 3] tâm trạng =[1, 1, 0, 0, 0] k =2, thì đầu ra sẽ là 17 vì nếu chúng ta đặt tâm trạng [2 ] và tâm trạng [3] thành 1, thì tổng tâm trạng sẽ là 2 + 3 + 6 + 6 =17 khách hàng hài lòng.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- n:=kích thước của tâm trạng
- a:=danh sách kích thước (n + 1) và điền bằng 0
- s:=0
- đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
- a [i + 1]:=a [i]
- nếu tâm trạng [i] khác 0, thì
- s:=s + khách hàng [i]
- nếu không,
- a [i + 1]:=a [i + 1] + khách hàng [i]
- d:=0
- đối với tôi trong phạm vi từ k đến n, thực hiện
- d:=tối đa của d và (a [i] - a [i - k])
- return s + d
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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 customers = [2, 3, 6, 6, 3] mood = [1, 1, 0, 0, 0] k = 2 print(solve(customers, mood, k))
Đầu vào
[2, 3, 6, 6, 3], [1, 1, 0, 0, 0], 2
Đầu ra
17