难题本 | LeetCode5667. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？

我的第一次LeetCode周赛，本来大有希望AC三道题，结果在这个神坑上趴了半个多小时o(╥﹏╥)o

题目链接：https://leetcode-cn.com/problems/can-you-eat-your-favorite-candy-on-your-favorite-day/

题目

给你一个下标从 0 开始的正整数数组 candiesCount ，其中 candiesCount[i] 表示你拥有的第 i 类糖果的数目。同时给你一个二维数组 queries ，其中 queries[i] = [favoriteTypei, favoriteDayi, dailyCapi] 。

你按照如下规则进行一场游戏：

你从第 0 天开始吃糖果。

你在吃完所有第 i - 1 类糖果之前，不能吃任何一颗第 i 类糖果。

在吃完所有糖果之前，你必须每天至少吃一颗糖果。

请你构建一个布尔型数组 answer ，满足 answer.length == queries.length 。answer[i] 为 true 的条件是：在每天吃 不超过 dailyCapi 颗糖果的前提下，你可以在第 favoriteDayi 天吃到第favoriteTypei类糖果；否则 answer[i] 为 false 。注意，只要满足上面 3 条规则中的第二条规则，你就可以在同一天吃不同类型的糖果。

请你返回得到的数组 answer 。

示例1

输入：candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]

输出：[true,false,true]

示例2

输入：candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]

输出：[false,true,true,false,false]

数据范围

1 <= candiesCount.length <= 105

1 <= candiesCount[i] <= 105

1 <= queries.length <= 105

queries[i].length == 3

0 <= favoriteTypei < candiesCount.length

0 <= favoriteDayi <= 109

1 <= dailyCapi <= 109

分析

弯弯绕绕的规则，实际上就是在问：从头开始吃，能不能在第favDay天吃到favType这种糖果。

由于从第0天开始吃，所以在favDay这一天的时候，前面一共也已经吃了favDay天。

这么多天里，最多能吃掉多少糖果，最少能吃掉多少糖果呢？非常简单：

每个query里面给出了每天最多能吃多少糖果，我的程序中记做dayCap；

每天敞开了吃，不算favDay这一天，最多吃掉favDat * dayCap的糖果，算上这一天结束，能吃掉(favDay + 1) * dayCap的糖果；

每天省着吃，但是规定至少需要吃掉一颗。不算favDay这一天，最少也得吃掉favDay的糖果。

由于从前往后吃，所以在favDay这一天能不能吃到favType这类糖果，就转化为了favType之前的所有糖果的数量和与上面这两个数值的关系。吃不到糖果只有两种可能，太多与太少：

当我们敞开了吃，结果在favDay这一天结束的时候都没办法吃到第favType类糖果，这是由于它前面类型的糖果数量太多了；

当我们省着吃，结果在favDay这一天之前就已经把favType类糖果吃完了，这是由于它前面类型的糖果数量太少了；

使用前缀和数组保存favType之前的糖果数量和，prefix_sum[i]表示第i类糖果之前的糖果和（不包括第i类）。

AC代码

class Solution:
    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:
        res = []
        prefix_sum = [0]
        for i in range(1, len(candiesCount) + 1):
            prefix_sum.append(prefix_sum[-1] + candiesCount[i - 1])
            
        # print(len(prefix_sum))
        
        for q in queries:
            favType = q[0]
            favDay = q[1]
            dayCap = q[2]
            
            # 敞开了吃，都不能在favDay结束的时候把前面的糖果吃完
            # 这里需要算上favDay，一共吃favDay + 1天
            if (favDay + 1) * dayCap <= prefix_sum[favType]:
                res.append(False)
                continue
            # 省着吃，在favDay之前就已经把favType吃完
            if favDay >= prefix_sum[favType + 1]:
                res.append(False)
                continue
            res.append(True)
            
        return res

class Solution {
public:
    typedef long long LL;
    
    vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
        LL prefix_sum[100010] = { 0 };
        // prefix_sum[i]: candiesCount[0]加到candiesCount[i - 1]
        
        bool check = false;
        for (int i = 1; i <= candiesCount.size(); ++i)
        {
            prefix_sum[i] = prefix_sum[i - 1] + candiesCount[i - 1];
            // cout << "i = " << i << ": " << prefix_sum[i] << " ";
        }
        
        LL favDay, favType, dayCap;
        vector<bool> res;
        for (auto t : queries)
        {
            favDay = t[1];
            favType = t[0];
            dayCap = t[2];
            
            // 第favDay之前，一共吃了favDay天
            // 每天开足马力吃，都吃不完前面的
            // prefix_sum[favType] = candiesCount[0] 加到 candiesCount[favType - 1]
            // 即开始吃favType之前的糖果总和
            if ((favDay + 1) * dayCap <= prefix_sum[favType])
            {
                res.push_back(false);
                continue;
            }
            // 每天省着吃，都吃不够
            if (favDay >= prefix_sum[favType + 1])
            {
                res.push_back(false);
                continue;
            }
            res.push_back(true);
        }
        
        return res;
    }
};

数据层面，我看讨论区讲的最多的是int存不下的坑，其实这道题从看到数据的第一眼开始就应该选择使用long或long long，大佬们的低级错误啊~

然后是从第0天开始吃的问题，加粗也拯救不了眼瞎…

之前WA了几次，还是逻辑上的错误，没有考虑到favDay这一天也是能吃的，所以最大数量少算了一天；就这还能过61/62，测试数据有点弱。

关键测试组：

Input:

[46,5,47,48,43,34,15,26,11,25,41,47,15,25,16,50,32,42,32,21,36,34,50,45,46,15,46,38,50,12,3,26,26,16,23,1,4,48,47,

32,47,16,33,23,38,2,19,50,6,19,29,3,27,12,6,22,33,28,7,10,12,8,13,24,21,38,43,26,35,18,34,3,14,48,50,34,38,4,50,26,

5,35,11,2,35,9,11,31,36,20,21,37,18,34,34,10,21,8,5]

[[85,54,42]]

Output:

true