wat constraints does dis bring in the question... "Also the books are
arranged in a certain order and this order must never be changed."
does this imply ---> a student gets only consecutivly numbered book
if not then---->
sort the array B in decreasing order in Onlogn
take another array S of k elements
traverse B(sorted)
S[i]=B[i]
when first k elemnts traversed then traverse again k elemnts of B and
S[2*k-i]+=B[i])...again S[i-2*k]+=B[i][.so on till B is traversed
completely......
On Sat, Jun 16, 2012 at 2:22 AM, Hemesh Singh <hemesh.mn...@gmail.com>wrote:
> 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
> <dayanidhi.haris...@gmail.com>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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
