【Leetcode】1052. Grumpy Bookstore Owner

题目地址：

https://leetcode.com/problems/grumpy-bookstore-owner/description/

给定一个两个长都是$n$的数组$c$和$g$，$c$是代表每天顾客的满意值，$g$代表每天店长是否生气，$0$代表生气，$1$代表不生气。店长不生气的那天，可以取得满意值；否则不能取得满意值。店长可以发动技能，使得连续$x$天都不生气，但最多只能发动一次。问$n$天内他能得到的顾客总满意值总和最大是多少。

我们考虑发动一次技能能最多多得多少满意度，这个其实就是求数组$[c_i{g}_i]$的长$x$的区间最大和，可以直接扫描一遍得出。原本的满意度总和为数组$[c_i(1-g_i)]$的总和，原本总和加上新增的即为新的最大总和。代码如下：

class Solution {
 public:
  int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
    int res = 0, n = customers.size();
    for (int i = 0, s = 0; i < n; i++) {
      s += grumpy[i] * customers[i];
      if (i >= minutes) s -= grumpy[i - minutes] * customers[i - minutes];
      res = max(res, s);
    }

    for (int i = 0; i < n; i++) res += !grumpy[i] * customers[i];

    return res;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度$O(n)$，空间$O(1)$。