您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

六一特供--你能在你最喜欢的那天吃到最喜欢的糖果吗?

文章目录

  • 题目
  • 题目的解读
  • 解题代码

题目

在这里插入图片描述

题目的解读

可能初看题目有些懵逼,实际上就是给了类型糖果的数组(下标表示第几类,其中的值表示有多少个这种类型糖果)。以及一个queries(查询数组)用于查询这个人最喜欢的糖果类型、最喜欢的是哪一天(从0开始计数的天数)、这个人每一天最多吃下多少的糖果

然后题目的目的是需要根据queries数组中的各个人的要求返回他们是否能够满足在最喜欢的那一天吃到最喜欢的糖果类型

根据题意,注意这三点:

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

解题方法:通过计算一直到你喜欢的那天中你所能吃下的糖果总数的范围,比如需要判断能否在第i天吃下最喜欢的糖果类型j,那么它这么多天能吃下的糖果范围是[i+1,(i+1)*capacity],而要能吃到第j类的糖果,我们至少需要吃到的糖果总数范围是[sum[j-1]+1,sum[j]],特别的范围:当为第0类时为[1,sum[j]].
至此我们只需要计算这两个区间是否含有交集,一旦含有交集,就能在最喜欢的那天吃到最喜欢的糖果

解题代码

class Solution {
public:
    vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
        int n = candiesCount.size();
        long long sum[n];
        memset(sum,0,sizeof(sum));
        //让sum[i]表示类型0一直到类型i的糖果的总数(需要long long防止溢出)
        for(int i=0;i<n;i++){
            sum[i] = candiesCount[i];
            if(i>0)
            sum[i] += sum[i-1];
        }
        vector<bool>res;
        for(auto q:queries){
            int favType = q[0];
            int favDay = q[1];
            int dayCap = q[2];
            //开始计算需要的范围
            long long x1 = favDay+1;
            long long y1 = (long long)(favDay+1)*dayCap;
            long long x2 = favType==0?1:sum[favType-1]+1;
            long long y2 = sum[favType];
            //很明显,当y1<x2或者是y2<x1时无任何交集
            res.push_back(!(y1<x2||y2<x1));
        }
        return res;
    }
};



分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进