At first look it appears to be a simple problem of discrete binary search. Take sum of b[i] as the upper_bound and 0 as the lower bound. Then apply a simple binary search for the number of pages that can be given to a student. Complexity : O(N log( sum( B ) ) )
On Thu, Jun 14, 2012 at 12:26 PM, algogeek <[email protected]>wrote: > In a library there are N books with the number of pages in i th book given > by bi . These books are to be distributed among K students such that the > difference between the largest sum of pages in the books assigned to any > student and the smallest sum of number of pages in the books assigned to > any student is minimum for the given input. Also the books are arranged in > a certain order and this order must never be changed. > For eg: > suppose B[ ] contains the number of pages in each book. > then > N=6 > K=3 > B={3,7,8,2,6,4} > > then the output will be 0 as we can give book 1 and 2 to student 1 and > book 3 and 4 to student 2 and the remaining to student 3. That makes 10 > pages for student 1 10 for 2 and 10 for 3 and thus the difference is 0 > > similarly if B={3,6,8,2,6,4} then the minimum difference will be 1 . > > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/JjKITS_gN9UJ. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Hemesh singh -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
