每日一题 1052

1052. 爱生气的书店老板

今天,书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客(customers[i])会进入书店,所有这些顾客都会在那一分钟结束后离开。

在某些时候,书店老板会生气。 如果书店老板在第 i 分钟生气,那么 grumpy[i] = 1,否则 grumpy[i] = 0。 当书店老板生气时,那一分钟的顾客就会不满意,不生气则他们是满意的。

书店老板知道一个秘密技巧,能抑制自己的情绪,可以让自己连续 X 分钟不生气,但却只能使用一次。

请你返回这一天营业下来,最多有多少客户能够感到满意的数量

思路
  • 分成两步做

    1. 算出老板不生气情况下,所有满意的顾客数量
    2. 算出窗口X内,因为生气不满意的顾客数目
class Solution {
public:
    int maxSatisfied(vector& customers, vector& grumpy, int X) {
        int res1 = 0;//最终满意的用户数量
        //分成两步
        //1. 在不生气情况下所有顾客数目
        for (int i = 0; i < grumpy.size(); i++) {
            if (grumpy[i] == 0) {
                res1 += customers[i];
            }
        }
        //2. 窗口X内因为生气赶走的顾客数目
        // 求出每个范围内留下顾客的最大值
        int resvalue = 0, curvalue = 0;
        for (int i = 0; i < X; i++) {
            if (grumpy[i] == 1) {
                curvalue += customers[i];
            }
        }
        resvalue = curvalue;
        for (int i = X; i < customers.size(); i++) {
            if (grumpy[i] == 1) {
                curvalue += customers[i];
            }
            if (grumpy[i-X] == 1) {
                curvalue -= customers[i-X];
            }
            resvalue = max(resvalue, curvalue);
        }
        return res1 + resvalue;
    }
};

你可能感兴趣的