【Leetcode】1052. Grumpy Bookstore Owner（138周赛第二题）（模拟）

以你之姓@ 2022-01-27 11:09 161阅读 0赞

Today, the bookstore owner has a store open for `customers.length` minutes. Every minute, some number of customers (`customers[i]`) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, `grumpy[i] = 1`, otherwise `grumpy[i] = 0`. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for `X` minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

**Example 1:**

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
    Output: 16
    Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes. 
    The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

**Note:**

*  `1 <= X <= customers.length == grumpy.length <= 20000`
 *  `0 <= customers[i] <= 1000`
 *  `0 <= grumpy[i] <= 1`

题目大意：

customers表示这个时间段内会有多少个客户在商店内，grumpy表示老板是否生气如果生气则客户的就会不满意，但是给出一个X表示可以在这个时间段内变得不生气，求解最多会有多少顾客满意。

解题思路：

暴力即可。

若X大于整个的时间段，则我们将输出全部客户的满意度。

否组，先对原有的customers数组进行处理，将boss生气的部分置为负数，统计此时最大的满意度。之后遍历数组，计算X区间内最大满意度加上原有不满意的部分，最终求解最大值。

class Solution {
    public:
        int maxSatisfied(vector<int>& c, vector<int>& g, int X) {
            int n = c.size();
            int sum_c_good = 0;
            int sum_c_bad = 0;
            for(int i = 0;i<n;i++){
                sum_c_good += c[i];
                if(g[i]==1){
                    c[i] *= -1; 
                }else{
                    sum_c_bad += c[i];
                }
            }
            int ans = sum_c_bad;
            if(X>=n){
                ans = sum_c_good;
            }else{
                for(int i=0;i<=n-X;i++){
                    int tmp_idx = i;
                    int cor_sum = 0;
                    int tmp_sum_c_bad = sum_c_bad;
                    for(int j=0;j<X;j++){
                        if(c[tmp_idx+j]<0){
                            tmp_sum_c_bad += abs(c[tmp_idx+j]);
                        }
                    }
                    ans = max(tmp_sum_c_bad, ans);
                }
            }
            
            return ans;
        }
    };