Grumpy Bookstore Owner: Cửa Hàng Sách, Chủ Không Vui, Kỹ Thuật Giữ Bình Tĩnh X Phút

Đề bài: Mỗi phút i: customers[i] khách vào, grumpy[i]=1 nghĩa là chủ không vui → khách không hài lòng. Chủ có kỹ thuật giữ bình tĩnh X phút liên tục (dùng 1 lần). Tối đa hóa khách hài lòng.

Ví dụ: customers=[1,0,1,2,1,1,7,5], grumpy=[0,1,0,1,0,1,0,1], X=3 → 16.

Ý tưởng: Sliding Window Tìm Khoảng X Phút Tối Ưu

Khách hài lòng mặc định = sum customers[i] где grumpy[i]=0.

Kỹ thuật biến grumpy[i]=1 → 0 trong cửa sổ X phút → thêm được customers[i] cho những i có grumpy[i]=1 trong cửa sổ.

→ Tìm cửa sổ độ dài X có tổng customers[i] * grumpy[i] lớn nhất.

Code Python

class Solution:
    def maxSatisfied(self, customers: list[int], grumpy: list[int], X: int) -> int:
        n = len(customers)
        
        # Base satisfied customers (grumpy=0)
        base = sum(c for c, g in zip(customers, grumpy) if g == 0)
        
        # Sliding window: extra satisfied if we "fix" grumpy in window
        extra = sum(customers[i] for i in range(X) if grumpy[i] == 1)
        max_extra = extra
        
        for i in range(X, n):
            # Remove left
            if grumpy[i-X] == 1:
                extra -= customers[i-X]
            # Add right
            if grumpy[i] == 1:
                extra += customers[i]
            max_extra = max(max_extra, extra)
        
        return base + max_extra

# Test
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

Phân tích

• Time: O(n) - single pass sliding window.
• Space: O(1).
• Base + max_extra = total max satisfied.

Kết luận

Sliding window trên "lợi ích thêm được" (customers[i] where grumpy[i]=1). Pattern: fixed window max sum → sliding window O(n).