고객 목록과 또 다른 목록 분위기가 있다고 가정하고 이 둘은 길이가 같고 또 다른 정수 k가 있습니다. 이제 매분 i에서 고객[i]의 수는 매장을 방문하고 기분[i] =1이면 고객이 행복하다는 것을 나타내고 기분[i] =0이면 슬퍼합니다. k 크기의 무드 하위 목록을 1로 설정할 수 있으며, 마지막으로 우리가 행복하게 만들 수 있는 최대 사람 수를 찾아야 합니다.
따라서 입력이 고객 =[2, 3, 6, 6, 3] 분위기 =[1, 1, 0, 0, 0] k =2인 경우 출력은 17이 됩니다. 왜냐하면 우리가 분위기[2를 설정하면 ] 및 분위기[3]를 1로 변경하면 총 분위기는 2 + 3 + 6 + 6 =17명의 고객이 만족합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=기분의 크기
- a :=크기 목록(n + 1) 및 0으로 채우기
- s :=0
- 0 ~ n - 1 범위의 i에 대해
- a[i + 1] :=a[i]
- mood[i]가 0이 아니면
- s :=s + 고객[i]
- 그렇지 않으면
- a[i + 1] :=a[i + 1] + 고객[i]
- d :=0
- k~n 범위의 i에 대해 다음을 수행합니다.
- d :=d의 최대값 및 (a[i] - a[i - k])
- s + d를 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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))
입력
[2, 3, 6, 6, 3], [1, 1, 0, 0, 0], 2
출력
17