Book Allocation Problem (Allocate minimum number of pages)
Given an array of integers A of size N and an integer B. College library has N bags, the ith book has A[i] number of pages.
You have to allocate books to B number of students so that the maximum number of pages allocated to a student is minimum. A book will be allocated to exactly one student. Each student has to be allocated at least one book. Allotment should be in contiguous order, for example, A student cannot be allocated book 1 and book 3, skipping book 2. Calculate and return that minimum possible number. Return -1 if a valid assignment is not possible.
Input:
The first line contains T denoting the number of test cases. Then follows a description of T test cases: Each case begins with a single positive integer N denoting the number of books. The second line contains N space-separated positive integers denoting the pages of each book. And the third line contains another integer B, denoting the number of students.
Output:
For each test case, output a single line containing the minimum number of pages each student has to read for the corresponding test case.
Examples:
INPUT:
T=1
N=4
[10,20,30,40]
B=2
OUTPUT:
60, one student assigned 60 pages and other 40.
INPUT:
T=1
N=4
[12 34 67 90]
B=2
OUTPUT:
113, one student assigned 113 pages and other 90.
We will use the logic that the pages can be assigned in increasing order manner since one student can have the maximum number of pages as the sum of pages of all the books (which is practically not possible here as we need to assign something to every candidate) and to divide the page in an optimal manner we need to have a max of all the pages of different books to be assigned to some student and remaining pages should be distributed to other students so that the maximum amount of pages assigned to a student is minimum.
So the constraint for binary search start and end is solved by taking start as the max of pages of the given book and end will be the sum of all the pages from all books.
We will keep using the binary search method and each time we take mid as the pivot we check if that is the maximum number of pages which can be assigned to the B number of student optimally.
We declare a bool function isValid which will check if the current number of pages that we pass into it is a valid case of not is it satisfy the condition then we return true and then check the maximum of currently assigned pages and new assigned pages.
One more condition to check is the number of students and the number of books if the number of students is greater than the number of books then we return false to isValid condition.
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer