1744. Can You Eat Your Favorite Candy on Your Favorite Day

# 1744. Can You Eat Your Favorite Candy on Your Favorite Day?#

## 题目 #

You are given a (0-indexed) array of positive integers `candiesCount` where `candiesCount[i]` represents the number of candies of the `ith` type you have. You are also given a 2D array `queries` where `queries[i] = [favoriteTypei, favoriteDayi, dailyCapi]`.

You play a game with the following rules:

• You start eating candies on day `0`.
• You cannot eat any candy of type `i` unless you have eaten all candies of type `i - 1`.
• You must eat at least one candy per day until you have eaten all the candies.

Construct a boolean array `answer` such that `answer.length == queries.length` and `answer[i]` is `true` if you can eat a candy of type `favoriteTypei` on day `favoriteDayi` without eating more than `dailyCapi` candies on any day, and `false` otherwise. Note that you can eat different types of candy on the same day, provided that you follow rule 2.

Return the constructed array `answer`.

Example 1:

``````Input: candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
Output: [true,false,true]
Explanation:
1- If you eat 2 candies (type 0) on day 0 and 2 candies (type 0) on day 1, you will eat a candy of type 0 on day 2.
2- You can eat at most 4 candies each day.
If you eat 4 candies every day, you will eat 4 candies (type 0) on day 0 and 4 candies (type 0 and type 1) on day 1.
On day 2, you can only eat 4 candies (type 1 and type 2), so you cannot eat a candy of type 4 on day 2.
3- If you eat 1 candy each day, you will eat a candy of type 2 on day 13.
``````

Example 2:

``````Input: candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
Output: [false,true,true,false,false]
``````

Constraints:

• `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`

## 题目大意 #

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

## 解题思路 #

• 每天吃糖个数的下限是 1 颗，上限是 dailyCap。针对每一个 query 查询在第 i 天能否吃到 i 类型的糖果，要想吃到 i 类型的糖果，必须吃完 i-1 类型的糖果。意味着在 [favoriteDayi + 1, (favoriteDayi+1)×dailyCapi] 区间内能否包含一颗第 favoriteTypei 类型的糖果。如果能包含则输出 true，不能包含则输出 false。吃的糖果数是累积的，所以这里利用前缀和计算出累积吃糖果数所在区间 [sum[favoriteTypei−1]+1, sum[favoriteTypei]]。最后判断 query 区间和累积吃糖果数的区间是否有重叠即可。如果重叠即输出 true。
• 判断两个区间是否重合，情况有好几种：内包含，全包含，半包含等等。没有交集的情况比较少，所以可以用排除法。对于区间 [x1, y1] 以及 [x2, y2]，它们没有交集当且仅当 x1 > y2 或者 y1 < x2。

## 代码 #

``````package leetcode

func canEat(candiesCount []int, queries [][]int) []bool {
n := len(candiesCount)
prefixSum := make([]int, n)
prefixSum[0] = candiesCount[0]
for i := 1; i < n; i++ {
prefixSum[i] = prefixSum[i-1] + candiesCount[i]
}
res := make([]bool, len(queries))
for i, q := range queries {
favoriteType, favoriteDay, dailyCap := q[0], q[1], q[2]
x1 := favoriteDay + 1
y1 := (favoriteDay + 1) * dailyCap
x2 := 1
if favoriteType > 0 {
x2 = prefixSum[favoriteType-1] + 1
}
y2 := prefixSum[favoriteType]
res[i] = !(x1 > y2 || y1 < x2)
}
return res
}
``````

Apr 8, 2023