滑动窗口的题目有一个套路，可以通过在上一个窗口中维护的值计算出当前窗口中的值。一般需要用到累加和还有错位相减来推出递推公式。

本题中，记 fi=∑j=i−X+1ici⋅gif_i = \sum_{j=i-X+1}^{i} c_i \cdot g_i。其中 fif_i 表示当前窗口能够增加多少满意的顾客，cic_i 表示第 i 分钟店内的顾客数，gig_i 表示第 i 分钟老板是否生气。相乘的含义是如果老板在 i 分钟生气但忍住，就能增加 cic_i 个顾客满意度。

那么 fi−1=∑j=i−Xi−1ci−1⋅gi−1f_{i-1} = \sum_{j=i-X}^{i-1} c_{i-1} \cdot g_{i-1}

fi−fi−1=ci⋅gi−ci−X⋅gi−Xf_i - f_{i-1} = c_i \cdot g_i - c_{i-X} \cdot g_{i-X}

fi=fi−1+ci⋅gi−ci−X⋅gi−Xf_i = f_{i-1} + c_i \cdot g_i - c_{i-X} \cdot g_{i-X}

原题链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxSatisfied(vector<int>& c, vector<int>& g, int X) {
        int n = c.size();
        int base = 0;
        for(int i=0;i<n;i++) {
            base = base + c[i] * !g[i];
        }
        int inc = 0;
        for(int i=0;i<X;i++) {
            inc += g[i] * c[i];
        }
        int ma = inc;
        for(int i=X;i<n;i++) {
            inc = inc + c[i]*g[i] - c[i-X]*g[i-X];
            ma = max(ma, inc);
        }
        return ma + base;
    }
};