leetcode-1744-你能在你最喜欢那天迟到你最喜欢的糖果吗？

你能在你最喜欢那天迟到你最喜欢的糖果吗？

题面

leetcode题目

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

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

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

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

请你返回得到的数组 \(answer\) 。

example

输入：\(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\) 的糖果。

数据范围

• \(1 <= candiesCount.length <= 10^5\)
• \(1 <= candiesCount[i] <= 10^5\)
• \(1 <= queries.length <= 10^5\)
• \(queries[i].length == 3\)
• \(0 <= favoriteType_i < candiesCount.length\)
• \(0 <= favoriteDay_i <= 10^9\)
• \(1 <= dailyCap_i <= 10^9\)

题解

总体思路

这个题粗看之下很容易会想去dp求一个在满足最大\(dailyCap\)时是否能在第\(favoriteDay\)天吃到\(favoriteType\), 但是仔细看一下题目数据范围就会放弃掉这个想法。
既然没办法做dp,那我们来仔细考虑每一组查询，在每组查询中，我们都很容易发现只要\(favoriteDay\)满足\(min \leq favoriteDay \leq max\) 其中\(min\)和\(max\)分别是吃到\(favoriteType\)所需的最小天数和最大天数，那么就能满足题目给出的条件。
我们再考虑如何去求出\(max\)和\(min\)，显然\(min\)在每天吃\(1\)颗糖果时得出，\(max\)在每天吃\(dailyCap\)颗糖果时得出。那么我们假设\(sum_i\)表示吃完前\(i\)类糖果所需要吃的糖果数量，则\(min = sum_i - 1\)，\(max = \lfloor\frac{sum_{i-1}}{dailyCap}\rfloor\)。需要非常注意的是我们的天数是从\(0\)开始的！
再来考虑\(sum_i\)，显然\(sum\)使用前缀和维护。注意一下数据范围，会爆int。

代码

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <string>
#define _DEBUG
using namespace std;
class Solution
{
public:
    vector<bool> canEat(vector<int> &candiesCount, vector<vector<int>> &queries)
    {
        vector<bool> ret;
        int len = candiesCount.size();
        long long sum[len];
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < len; i++)
        {
            auto count = candiesCount[i];
            if (i == 0)
            {
                sum[i] = count;
            }
            else
            {
                sum[i] = sum[i - 1] + count;
            }
        }
        for (auto query = queries.begin(); query != queries.end(); query++)
        {
            auto favoriteType = (*query)[0];
            auto favoriteDay = (*query)[1];
            auto dailyCap = (*query)[2];
            long long count1, count2, max, min;
            count1 = count2 = max = min = 0;
            count2 = sum[favoriteType];
            if (favoriteType > 0)
            {
                count1 = sum[favoriteType - 1];
            }
            max = count2 - 1;
            min = (count1 / dailyCap);
#ifdef _DEBUG
            cout << "count1: " << count1 << " count2: " << count2 << " max: " << max << " min: " << min << endl;
#endif
            if (favoriteDay >= min && favoriteDay <= max)
            {
                ret.push_back(true);
            }
            else
            {
                ret.push_back(false);
            }
        }
        return ret;
    }
};

// for test
int main()
{
    Solution s;
    vector<int> count{16, 38, 8, 41, 30, 31, 14, 45, 3, 2, 24, 23, 38, 30, 31, 17, 35, 4, 9, 42, 28, 18, 37, 18, 14, 46, 11, 13, 19, 3, 5, 39, 24, 48, 20, 29, 4, 19, 36, 11, 28, 49, 38, 16, 23, 24, 4, 22, 29, 35, 45, 38, 37, 40, 2, 37, 8, 41, 33, 8, 40, 27, 13, 4, 33, 5, 8, 14, 19, 35, 31, 8, 8};
    vector<vector<int>> queries{
        {43, 1054, 49}};
    auto ret = s.canEat(count, queries);
    for (auto i = ret.begin(); i != ret.end(); i++)
    {
        cout << *i << " ";
    }
    cout << endl;
    return 0;
}