home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

Grumpy Bookstore Owner: หาลูกค้าที่พอใจสูงสุดด้วยเทคนิคไม่ขี้อ้อน X นาที

โจทย์

ร้านหนังสือเปิด n นาที นาที i มีลูกค้า customers[i] คน

  • เจ้าร้านขี้อ้อน (grumpy) นาที i: grumpy[i]=1 → ลูกค้านั้นไม่พอใจ
  • เจ้าร้านไม่ขี้อ้อน: grumpy[i]=0 → ลูกค้าพอใจ
  • เจ้าร้านมีเทคนิค "ไม่ขี้อ้อน" ใช้ได้ 1 ครั้ง ต่อเนื่อง X นาที

หา Maximum satisfied customers

ตัวอย่าง: customers=[1,0,1,2,1,1,7,5], grumpy=[0,1,0,1,0,1,0,1], X=3 → 16 (ใช้เทคนิคนาที 5-7: 1+7+5=13 เพิ่มจาก base)

อัลกอริทึม: Sliding Window + Base Satisfaction

  1. คำนวณ Base satisfied = ผลรวม customers[i] ที่ grumpy[i]=0 (พอใจอยู่แล้ว)
  2. หา Maximum additional satisfied จาก window ขนาด X:
    • Window เพิ่มได้เฉพาะนาทีที่ grumpy[i]=1 (เพราะ grumpy=0 นับใน base แล้ว)
    • Sliding window คำนวณ sum ของ customers[i] ที่ grumpy[i]=1 ใน window
  3. Answer = Base + Max additional

การติดตั้ง (Python Implementation)


class Solution:
    def maxSatisfied(self, customers: list[int], grumpy: list[int], X: int) -> int:
        n = len(customers)
        
        # 1. Base satisfied customers (grumpy=0)
        base = sum(c for c, g in zip(customers, grumpy) if g == 0)
        
        # 2. Sliding window for additional satisfied (grumpy=1)
        # Initial window [0, X-1]
        additional = sum(customers[i] for i in range(X) if grumpy[i] == 1)
        max_additional = additional
        
        # Slide window
        for i in range(X, n):
            # Remove leftmost
            if grumpy[i - X] == 1:
                additional -= customers[i - X]
            # Add new rightmost
            if grumpy[i] == 1:
                additional += customers[i]
            max_additional = max(max_additional, additional)
        
        return base + max_additional

# ทดสอบ
ob = Solution()
print(ob.maxSatisfied([1,0,1,2,1,1,7,5], [0,1,0,1,0,1,0,1], 3))  # 16
print(ob.maxSatisfied([1], [0], 1))                                  # 1
print(ob.maxSatisfied([4,10,10], [1,1,0], 2))                       # 24

Output

16
1
24

การวิเคราะห์ตัวอย่าง

i:     0  1  2  3  4  5  6  7
cust:  1  0  1  2  1  1  7  5
grump: 0  1  0  1  0  1  0  1

Base (grumpy=0): 1 + 1 + 1 + 7 = 10

Window size 3 (grumpy=1 only):
[0,1,2]: grumpy=[0,1,0] → add 0
[1,2,3]: grumpy=[1,0,1] → add 0+2=2
[2,3,4]: grumpy=[0,1,0] → add 2
[3,4,5]: grumpy=[1,0,1] → add 2+1=3
[4,5,6]: grumpy=[0,1,0] → add 1
[5,6,7]: grumpy=[1,0,1] → add 1+5=6 ← MAX

Total = 10 + 6 = 16 ✓

Complexity

  • Time: O(n) - Single pass base + sliding window
  • Space: O(1) - Constant extra space

สรุป

Grumpy Bookstore Owner = Sliding Window หา window ขนาด X ที่เพิ่ม satisfied customers มากที่สุด (เฉพาะนาทีที่ grumpy=1) บวกกับ base satisfied customers

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ