最喜欢的那天吃到你最喜欢的糖果吗?(medium)"/>
[前缀和]leetcode5667:你能在你最喜欢的那天吃到你最喜欢的糖果吗?(medium)
题目:
题解:
这道题是不难,md就是题目真tm难懂,我比赛时看到这么长的题目直接放弃了,求求能不能把题目写的简单好懂些。
思路:
- 先前缀和预处理,然后判断我们能吃到糖果的区间
[d+1,c*(d+1)]
,和我们想吃到糖果数的区间[s[t]+1,s[t+1]]
,二者是否存在交集。这里解释一下[s[t]+1,s[t+1]]
,由于种类 t 是从下标 0 开始的,而前缀和数组 s 是从下标 1 开始的,所以我们可以吃到种类 t 的糖果可以吃的最多糖果书为 s[t+1],吃的种类 t 的最少糖果数为 s[t]+1(表示糖果种类t-1
的下一个位置,也就是刚吃到种类i
的位置,种类t-1
对应最大位置为s[t]
,下一个位置为s[t]+1
)。
代码如下:
typedef long long LL;class Solution {
public:vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {int n=candiesCount.size();vector<LL> s(n+1,0);// 前缀和预处理for(int i=1;i<=n;++i)s[i]=s[i-1]+candiesCount[i-1];vector<bool> res;// 开始查询区间for(auto & q:queries){int t=q[0],d=q[1],c=q[2];// 当前可以吃到糖果数范围为[d+1,(d+1)*c],而自己想吃的糖果数范围为[s[t]+1,s[t+1]]// 解释:由于t的编号是从0开始的,而前缀和是从1开始的,所以下标t对应前缀和s中t+1,即第t种糖果吃到的最大糖果数为s[t+1],而吃到的最少糖果数就是下标t-1对应前缀和s的t的下一个位置,即为s[t]+1LL x1=d+1,y1=(LL)(d+1)*c;LL x2=s[t]+1,y2=s[t+1];// 判断[x1,y1] [x2,y2]是否有交集res.push_back(!(y1<x2||y2<x1));}return res;}
};
更多推荐
[前缀和]leetcode5667:你能在你最喜欢的那天吃到你最喜欢的糖果吗?(medium)
发布评论