help neede ... standard DP, Backtracking Problem
Разница между en1 и en2, 16 символ(ов) изменены
Problem :↵

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
 <br>
1 <= N, M <= 10^6
  <br>
1 <= A[i] <= 10^8
 <br>

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↵
array is : [ 3 4 5 5 8]↵
answer is : 9↵

how to solve? i didn’t figure out.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский n1e2m3 2019-05-29 08:33:12 1
en3 Английский n1e2m3 2019-05-28 20:11:35 104
en2 Английский n1e2m3 2019-05-28 20:10:04 16
en1 Английский n1e2m3 2019-05-28 20:09:05 1422 Initial revision (published)