โปรแกรมหาจำนวนคนสูงสุดที่ทำให้พอใจได้ใน Python

สมมติว่าเรามีรายการ customers และ mood ความยาวเท่ากัน และจำนวนเต็ม k ในแต่ละนาที i มีลูกค้า customers[i] คนมาที่ร้าน และ mood[i] = 1 แสดงว่าลูกค้าพอใจ mood[i] = 0 แสดงว่าเสียใจ เราสามารถตั้งค่าสับลิสต์ขนาด k ของ mood ให้เป็น 1 ทั้งหมด สุดท้ายเราต้องหาจำนวนคนสูงสุดที่ทำให้พอใจได้

เช่น ถ้าอินพุตคือ customers = [2, 3, 6, 6, 3], mood = [1, 1, 0, 0, 0], k = 2 ผลลัพธ์จะเป็น 17 เพราะถ้าตั้ง mood[2] และ mood[3] เป็น 1 ผลรวม mood จะเป็น 2 + 3 + 6 + 6 = 17 ลูกค้าพอใจ

ขั้นตอนการแก้ปัญหา

1. n := ขนาดของ mood
2. a := รายการขนาด (n+1) เติม 0, s := 0
3. สำหรับ i ในช่วง 0 ถึง n-1:
   • a[i+1] := a[i]
   • ถ้า mood[i] ไม่เป็นศูนย์: s := s + customers[i]
   • มิฉะนั้น: a[i+1] := a[i+1] + customers[i]
4. d := 0
5. สำหรับ i ในช่วง k ถึง n:
   • d := max(d, a[i] - a[i-k])
6. คืนค่า 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