第 226 场周赛 5667. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？

差2分钟做出来最后一题，好气！！rank 767

Desciption

有 n 类糖果，下标从 0 开始的正整数数组 candiesCount ，candiesCount[i] 表示第 i 类糖果的数目。 有一个询问数组 queries ，其中 queries[i] = [favoriteTypei, favoriteDayi, dailyCapi] 表示一个询问：在每天吃 不超过 dailyCapi 颗糖果的前提下，你可以在第 favoriteDayi 天吃到第 favoriteTypei 类糖果吗？

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

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

构造一个答案数组 answer 返回，answer[i] 为 true 表示第 i 个询问可以实现，为 false 表示不可以实现

输入：candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
输出：[true,false,true]

输入：candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
输出：[false,true,true,false,false]

Solution

很容易想到做法：

  1. 前缀和：表示前 i 类糖果的总和
  2. 二分：每天至少吃一颗，二分求出在 favoriteDayi 天，至少吃到哪类糖果 x；每天至多吃 dailyCapi 个，二分求出在 favoriteDayi 天，至多吃到哪类糖果 y。判断 favoriteTypei 是不是在 x 和 y 之间
  3. 坑点：第 0 天开始吃糖果，则在 favoriteDayi 天，至少要吃 favoriteDayi + 1 个糖果，至多吃 (favoriteDayi + 1) * dailyCapi 个糖果，二分要求的是第一个大于等于糖果数量的前缀和下标；糖果数组的下标从 0 开始（这个好像不是坑点，因为都是正整数且求的是大于等于的下标）

Code

    public int search(long val, long[] sum) {
        int L = 0, R = sum.length;
        while (L < R) {
            int mid = (L + R) >> 1;
            if (sum[mid] >= val) {
                R = mid;
            } else {
                L = mid + 1;
            }
        }
        return L - 1;
    }
    public boolean[] canEat(int[] candiesCount, int[][] queries) {
        int n = candiesCount.length, m = queries.length;
        long[] sum = new long[n + 1];
        sum[0] = 0;
        for (int i = 1; i <= n; ++i) {
            sum[i] = sum[i - 1] + candiesCount[i - 1];
        }

        boolean[] ans = new boolean[m];
        for (int i = 0; i < m; ++i) {
            int type = queries[i][0];
            int day = queries[i][1] + 1;
            int cc = queries[i][2];
            long mi = day, mx = 1L * day * cc;
            int L = search(mi, sum), R = search(mx, sum);
            if(L <= type && R >= type) {
                ans[i] = true;
            } else {
                ans[i] = false;
            }
            //System.out.println("ans[i] = " + ans[i]);
        }
        return ans;
    }