This is the time of Christmas and Santa wants to distribute gifts to M children. He has N number of boxes, and each box contains some chocolates. Now, Santa wants to distribute N boxes to M children keeping in mind that distribution should be as fair as possible. To fairly distribute the gift boxes, Santa wants to minimize the maximum number of choclates gifted to a child.
Formally, given M number of children and N boxes, where each box contains some amount of chocolates. The task is to minimize the maximum number of chocolate gifted to a child.
In another word, you have to divide array into M subset such that maximum sum of subset is minimized.
Input:
First line of input contains number of testcases T. For each testcase, there will be three lines of input. First line contains N number of gift boxes, next line contains choclates in each of the N boxes. Last line contains number of children.
Output:
For each testcase, print the minimum number of maximum chocolate a child get.
Constraints:
1 <= T <= 100
1 <= N, M <= 10^6
1 <= A[i] <= 10^8
Example:
Input:
1
4
12 34 67 200
3
Output:
200
Explanation:
Testcase 1: Minimum 200 chocolates will be given to a child which gets the maximum number of chocolate.
Another Corner Case : n = 5 and m=3
array is : [ 3 4 5 5 8]
answer is : 9
Sort the array in descending order. Now binary search on the answer. For a particular value check if the array can be divided into subsets with sum not exceeding that particular value.
You are right. i got your idea. but can you explain more on this statement …
" For a particular value check if the array can be divided into subsets with sum not exceeding that particular value. "
thank you for your reply.
Cool !
You can go through this JAVA code.
Basically what my check function does is to check if I can split the array into number of subsets less or equal to m such that the sum of each subset is <= threshold. So its optimal to choose the value which is just less than threshold value at each step.
Well my complexity for check function is O(NlogN), making the total complexity to be O(Nlog^2N), currently I don’t have any idea how to solve it in O(NlogN) or may be less.
Long just_smaller = map.floorKey(curr);
if(just_smaller == null){
cnt++;
curr = threshold;
continue;
}
if just_smaller == null, then value of curr is not change,
you assign again,curr = theshoold,
so just_smaller again make null and its infinite loop.