Chủ hiệu sách Grumpy bằng Python

Giả sử một chủ hiệu sách có một cửa hàng đang mở cửa với số lượng khách hàng ghi vào danh sách phút. Trong mỗi phút, một số khách hàng (khách hàng [i]) bước vào cửa hàng, sau đó tất cả những khách hàng đó rời đi sau khi kết thúc phút đó. Vào một số phút, chủ sở hữu là khó tính. Bây giờ nếu chủ hiệu sách gắt gỏng vào phút thứ i thì grumpy [i] =1, ngược lại grumpy [i] =0. Khi chủ hiệu sách gắt gỏng, khách hàng của phút đó không vui, ngược lại họ rất vui. Chủ hiệu sách biết một kỹ thuật để giữ cho mình không gắt gỏng trong X phút liên tục. Kỹ thuật đó không thể được sử dụng nhiều hơn một lần. Chúng tôi phải tìm ra số lượng khách hàng tối đa có thể vui vẻ suốt cả ngày. Vì vậy, nếu đầu vào là:khách hàng =[1,0,1,2,1,1,7,5] và gắt gỏng =[0,1,0,1,0,1] và X =3, thì đầu ra sẽ là 16. Điều này là do chủ sở hữu sẽ không gắt gỏng trong ba phút cuối cùng. Vì vậy, số lượng khách hàng hài lòng tối đa là 1 + 1 + 1 + 1 + 7 + 5 =16

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

đặt i:=0, j:=0, sums:=rỗng danh sách và tạm thời:=0
trong khi j - i + 1
- nếu grumpy [j] là 1 thì temp:=temp + customer [j]
- tăng j lên 1
chèn một danh sách [tạm thời, i, j] vào mảng tổng
tăng i và j lên 1
trong khi j <độ dài của danh sách khách hàng
- nếu grumpy [i - 1] là 1, thì temp:=temp - customer [i - 1]
- nếu grumpy [j] là 1 thì temp:=temp + customer [j]
- chèn một danh sách [tạm thời, i, j] vào mảng tổng
- tăng i và j lên 1
sums:=sắp xếp mảng tổng dựa trên phần tử đầu tiên của danh sách bên trong
index1:=phần tử thứ hai của danh sách cuối cùng tính bằng tổng, index2:=phần tử thứ ba của danh sách cuối cùng tính bằng tổng,
đối với tôi trong phạm vi index1 đến index2 đặt grumpy [i]:=0
ans:=0
cho tôi trong phạm vi từ 0 đến chiều dài khách hàng
- nếu grumpy [i] là 0 thì ans:=ans + customer [i]
trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

class Solution(object):
   def maxSatisfied(self, customers, grumpy, X):
      i = 0
      j = 0
      sums = []
      temp = 0
      while j-i+1<X:
         if grumpy[j]:
            temp+=customers[j]
         j+=1
      sums.append([temp,i,j])
      i+=1
      j+=1
      while j<len(customers):
         if grumpy[i-1]:
            temp-=customers[i-1]
         if grumpy[j]:
            temp+=customers[j]
         sums.append([temp,i,j])
         i+=1
         j+=1
      sums =sorted(sums,key = lambda v : v[0])
      index1 = sums[-1][1]
      index2 = sums[-1][2]
      for i in range(index1,index2+1):
         grumpy[i] = 0
      ans = 0
      for i in range(len(customers)):
         if not grumpy[i]:
            ans+=customers[i]
      return ans
ob = Solution()
print(ob.maxSatisfied([1,0,1,2,1,1,7,5],[0,1,0,1,0,1,0,1],3))

Đầu vào

[1,0,1,2,1,1,7,5]
[0,1,0,1,0,1,0,1]
3

Chủ hiệu sách Grumpy bằng Python

Ví dụ

Đầu vào

Đầu ra