สมมติว่าเรามีรายชื่อลูกค้าและอารมณ์รายการอื่น สองตัวนี้มีความยาวเท่ากัน เรามีจำนวนเต็ม 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 ทำ
- a[i + 1] :=a[i]
- ถ้าอารมณ์[i]ไม่ใช่ศูนย์ แล้ว
- s :=s + ลูกค้า[i]
- มิฉะนั้น
- a[i + 1] :=a[i + 1] + ลูกค้า[i]
- d :=0
- สำหรับฉันอยู่ในช่วง k ถึง n ทำ
- 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
