分糖果 | HReina

分糖果I (easy)、分糖果 II (easy)、每个小孩最多能分到多少糖果 (medium)、分发糖果 (hard)

575.分糖果 I (easy)

Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。

医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。

给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的最多种类数。

示例1：
1
2
3
输入：candyType = [1,1,2,2,3,3]
输出：3
解释：Alice 只能吃 6 / 2 = 3 枚糖，由于只有 3 种糖，她可以每种吃一枚。

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        int n=candyType.size();
        set<int> st;
        for(int i=0;i<n;i++){
            st.insert(candyType[i]);
        }
        int res=st.size();
        return min(res, n/2);
    }
};

1103.分糖果 II (easy)

排排坐，分糖果。

我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。

给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。

然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。

重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。

返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。

示例1：
1
2
3
4
5
6
7
输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。

class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        vector<int> res(num_people);
        int k=1;
        for(int i=0;i<1000000000;i++){
            if(k<=candies){
                res[i%num_people] +=k;
                candies -=k;
                k++;
            }else{
                res[i%num_people] +=candies;
                break;
            }
        }
        return res;
    }
};

2226.每个小孩最多能分到多少糖果 (medium)

给你一个下标从 0 开始的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的子堆，但无法再将两堆合并到一起。

另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到相同数量的糖果。每个小孩可以拿走至多一堆糖果，有些糖果可能会不被分配。

返回每个小孩可以拿走的最大糖果数目。

示例1：

输入：candies = [5,8,6], k = 3
输出：5
解释：可以将 candies[1] 分成大小分别为 5 和 3 的两堆，然后把 candies[2] 分成大小分别为 5 和 1 的两堆。现在就有五堆大小分别为 5、5、3、5 和 1 的糖果。可以把 3 堆大小为 5 的糖果分给 3 个小孩。可以证明无法让每个小孩得到超过 5 颗糖果。

class Solution {
public:
    int maximumCandies(vector<int>& candies, long long k) {
        int n=candies.size();
        int maxVal=0;
        for(int i=0;i<n;i++){
            if(candies[i]>maxVal){
                maxVal=candies[i];
            }
        }
        int left=1; 
        int right=maxVal;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(fun(candies, k, mid)){
                left=mid+1;
            }else{
                right=mid-1;
            }
        } 
        return right;
    }
    bool fun(vector<int>& candies, long long k, int x){
        int n=candies.size();
        long long res=0;
        for(int i=0;i<n;i++){
            res += candies[i]/x; //注意x不能等于0；
        }
        return res>=k;
    }
};

135.分发糖果

思路：

将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理。

左规则：当ratings[i−1]<ratings[i] 时，i号学生的糖果数量将比i−1号孩子的糖果数量多。

右规则：当ratings[i]>ratings[i+1]时，i号学生的糖果数量将比i+1号孩子的糖果数量多。

class Solution {
public:
    int candy(vector<int>& ratings) {
        // 左规则：当ratings[i−1]<ratings[i] 时，i号学生的糖果数量将比i−1号孩子的糖果数量多。
        // 右规则：当ratings[i]>ratings[i+1] 时，i号学生的糖果数量将比i+1号孩子的糖果数量多。
        //两趟遍历
        int n=ratings.size();
        vector<int> left(n);
        int res=0;
        //从左往右遍历
        for(int i=0;i<n;i++){
            if(i>0 && ratings[i]>ratings[i-1]){
                left[i]=left[i-1]+1;
            }else{
                left[i]=1;
            }
        }
        //从右往左遍历
        for(int i=n-1;i>=0;i--){
            if(i<n-1 && ratings[i]>ratings[i+1] && left[i]<=left[i+1]){
                left[i]=left[i+1]+1;
            }
        }
        for(int i=0;i<n;i++){
            res += left[i];
        }
        return res;
    }
};