# 1744.你能在你最喜欢的那天吃到你最喜欢的糖果吗？ (Medium)

## 问题描述
[1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？ (Medium)](https://leetcode.cn/problems/can-you-eat-your-favorite-candy-on-your-favorite-day/)

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

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

- 你从第 `0` 天开始吃糖果。
- 你在吃完 **所有** 第 `i - 1` 类糖果之前， **不能** 吃任何一颗第 `i` 类糖果。
- 在吃完所有糖果之前，你必须每天 **至少** 吃 **一颗** 糖果。

请你构建一个布尔型数组 `answer` ，用以给出 `queries` 中每一项的对应答案。此数组满足：

- `answer.length == queries.length` 。 `answer[i]` 是
`queries[i]` 的答案。
- `answer[i]` 为 `true` 的条件是：在每天吃 **不超过** `dailyCapᵢ`
颗糖果的前提下，你可以在第 `favoriteDayᵢ` 天吃到第 `favoriteTypeᵢ` 类糖果；否则
`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]
提示：
1- 在第 0 天吃 2 颗糖果(类型 0），第 1 天吃 2 颗糖果（类型 0），第 2 天你可以吃到类型 0
的糖果。
2- 每天你最多吃 4 颗糖果。即使第 0 天吃 4 颗糖果（类型 0），第 1 天吃 4 颗糖果（类型 0 和类型
1），你也没办法在第 2 天吃到类型 4 的糖果。换言之，你没法在每天吃 4 颗糖果的限制下在第 2 天吃到第 4
类糖果。
3- 如果你每天吃 1 颗糖果，你可以在第 13 天吃到类型 2 的糖果。

```

**示例 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 <= 10⁵`
- `1 <= candiesCount[i] <= 10⁵`
- `1 <= queries.length <= 10⁵`
- `queries[i].length == 3`
- `0 <= favoriteTypeᵢ < candiesCount.length`
- `0 <= favoriteDayᵢ <= 10⁹`
- `1 <= dailyCapᵢ <= 10⁹`

## 解题思路
见代码注释

## 代码
```cpp
class Solution {
  public:
    vector<bool> canEat(vector<int> &candiesCount, vector<vector<int>> &queries) {
        vector<long> prefix(candiesCount.size() + 1, 0);
        vector<bool> ans(queries.size(), 0);
        for (int i = 1; i <= candiesCount.size(); ++i) {
            prefix[i] = prefix[i - 1] + candiesCount[i - 1];
        }
        for (int i = 0; i < queries.size(); ++i) {
            int type = queries[i][0];
            int fday = queries[i][1];
            int cap = queries[i][2];
            // 要求fday天吃到type， 考虑吃不到的情况
            // fday天，就算吃最多，也吃不到type
            // 假设fday = 6，前面0，1，2，...，5已经吃了6天，type = 4，那么在第六天，一共七天，必须要能吃到type = 4的糖果，说明这七天能吃的糖果要大于prefix[4]（前4种糖果的数量）
            if ((long)(fday + 1) * cap <= prefix[type]) {
                ans[i] = false;
            } else if (prefix[type + 1] <= fday) {
                // 假设每天只吃1颗，也会提前吃完
                // 假设fday=6,type=4，那么前面吃了fday=6个，如果prefix[type+1] <= 6，此时0，1，2，3，4种都吃掉了
                // 第6天只能吃type=5了
                ans[i] = false;
            } else {
                ans[i] = true;
            }
        }
        return ans;
    }
};
```