เจ้าของร้านหนังสือไม่พอใจใน Python

สมมุติว่าเจ้าของร้านหนังสือเปิดร้านตามจำนวนลูกค้าที่เข้ารายการเป็นนาที ในแต่ละนาที ลูกค้าจำนวนหนึ่ง (ลูกค้า[i]) จะเข้ามาในร้าน หลังจากนั้นลูกค้าทั้งหมดจะออกจากร้านหลังจากสิ้นสุดนาทีนั้น เจ้าของไม่พอใจในบางนาที ตอนนี้ ถ้าเจ้าของร้านหนังสือไม่พอใจในนาทีที่ i ก็ให้ไม่พอใจ[i] =1 มิฉะนั้น ไม่พอใจ[i] =0 เมื่อเจ้าของร้านหนังสือไม่พอใจ ลูกค้าในนาทีนั้นจะไม่มีความสุข ไม่เช่นนั้น พวกเขาก็มีความสุข เจ้าของร้านหนังสือรู้เทคนิคเพื่อไม่ให้ตัวเองไม่พอใจเป็นเวลา X นาที เทคนิคนั้นไม่สามารถใช้ได้มากกว่าหนึ่งครั้ง เราต้องหาจำนวนลูกค้าให้มากที่สุดที่สามารถมีความสุขได้ตลอดทั้งวัน ดังนั้นหากอินพุตมีลักษณะดังนี้:ลูกค้า =[1,0,1,2,1,1,7,5] และไม่พอใจ =[0,1,0,1,0,1] และ X =3 ผลลัพธ์ จะอายุ 16 ปี นี่เป็นเพราะเจ้าของจะไม่ไม่พอใจในช่วงสามนาทีสุดท้าย ดังนั้นจำนวนลูกค้าที่มีความสุขสูงสุดคือ 1 + 1 + 1 + 1 + 7 + 5 =16

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• set i :=0, j :=0, sums :=รายการว่างและอุณหภูมิ :=0

• ในขณะที่ j – i + 1

  • ถ้า grumpy[j] คือ 1 แล้ว temp :=temp + customers[j]

  • เพิ่มขึ้น 1

• แทรกรายการ [temp, i, j] ลงในอาร์เรย์ผลรวม

• เพิ่ม i และ j ขึ้น 1

• ในขณะที่ j <ความยาวของรายชื่อลูกค้า

  • ถ้าไม่พอใจ[i - 1] คือ 1 แสดงว่า temp :=temp – customers[i - 1]

  • ถ้าไม่พอใจ[j] คือ 1 แล้ว temp :=temp + customer[j]

  • แทรกรายการ [temp, i, j] ลงในอาร์เรย์ผลรวม

  • เพิ่ม i และ j ขึ้น 1

• sums :=sort sums array ตามองค์ประกอบแรกของรายการภายใน

• index1 :=องค์ประกอบที่สองของรายการสุดท้ายในผลรวม index2 :=องค์ประกอบที่สามของรายการสุดท้ายในผลรวม

• สำหรับฉันอยู่ในช่วง index1 ถึง index2 ตั้งค่า grumpy[i] :=0

• ตอบ :=0

• สำหรับผมอยู่ในช่วง 0 ถึงความยาวของลูกค้า

  • ถ้า grumpy[i] เป็น 0 แล้ว ans :=ans + customers[i]

• กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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))

อินพุต

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

ผลลัพธ์

16