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.
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.
For each testcase, print the minimum number of maximum chocolate a child get.
1 <= T <= 100
1 <= N, M <= 10^6
1 <= A[i] <= 10^8
12 34 67 200
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
how to solve? i didn’t figure out.