语文题/贪心

查询是说每天至少吃1颗糖，最多吃c颗糖，是否能在第d天吃到第t类的糖。

则可得到第d天吃糖的数量是[d + 1, (d + 1) * c]。

因为糖是按照种类从左到右吃的，则第i类糖果是从第a[0] + a[1] + … + a[i - 1] + 1个到a[0] + a[1] + .... + a[i - 1] + a[i]，是否吃的到第t类的糖取决于是否有交集。

问题转换成了求两个区间是否有交集，求第i类糖果的区间可以用前缀和。

1. 初始化糖果前缀和
2. 对于每个查询，判断是否和第t类糖果有交集(吃的到第t类的糖)

时间复杂度$O(N + M)$,空间复杂度$O(N)$

AC代码

class Solution {
public:
    typedef long long LL;

    bool check(LL a, LL b, LL l, LL r) {
        if (a > r || l > b) return false;
        return true;
    }

    vector<bool> canEat(vector<int>& can, vector<vector<int>>& queries) {
        int n = can.size();
        //初始化前缀和
        vector<LL> s(n + 1);
        for (int i = 1 ; i <= n ; i ++) s[i] = s[i - 1] + can[i - 1];
        vector<bool> res;
        //处理每个查询
        for (auto& q : queries) {
            int t = q[0], d = q[1], c = q[2];
            res.push_back(check(d + 1, (LL)(d + 1) * c, s[t] + 1, s[t + 1]));
        }
        return res;
    }
};