2226. Maximum Candies Allocated to K Children

本文主要是介绍2226. Maximum Candies Allocated to K Children，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//题目和砍木头和875 koko吃香蕉一样
//画图画图画图重要的事情说三遍
// max NO. candies/pile
//candies 1 2 3 4 5 6 7 8

// 5 5 2 1 1 1 0 0 0
// 8 8 4 2 2 1 1 1 1
// 6 6 3 2 1 1 1 0 0

//Tot Candies 19 9 5 4 3 2 1 1

// 1. 二分法来处理这个问题，以每个篮子里多少个糖果来二分。
// 因为通过max No. candies/pile 可以计算出可以分出来多少篮子糖果。
//2. 二分的时候把通过Mid计算出来的篮子数目和 K个小朋友来对比
// 如果比K大，说明份的分数太多了。增加每个篮子里的糖果数目
// 如果比K小，说明分的分数太少。减少每个篮子里的糖果数目
// 3. 退出的时候，因为题目要求maximum number of candies each child can get
// 说明尽量每个篮子分的糖果多一些
// 比如假设每个篮子分7，8 个糖果分出来的篮子糖果一样，并且K也是1。那就得每个篮子分8个。、

class Solution {
public:
long long calcNumPiles(int numCandiesPerPile, vector<int>& candies){
long long ret = 0;

for(int candy: candies)
ret += candy / numCandiesPerPile;

return ret;
}

int maximumCandies(vector<int>& candies, long long k) {


int start = 1;
int maxCandiesPerPile = 0;

for(int candy: candies){
if(candy > maxCandiesPerPile)
maxCandiesPerPile = candy;
}

int end = maxCandiesPerPile;

while(start + 1 < end) {
int mid = start + (end - start) / 2;

long long numPiles = calcNumPiles(mid, candies);

if(numPiles >= k)
start = mid;
else
end = mid;
}

if(calcNumPiles(end, candies) >= k)
return end;
if(calcNumPiles(start, candies) >= k)
return start;

return 0;
}
};