The value of each object is different for every person.
For eg-
There are three people A,B and C and the value of each object for them are 3,4 and 5 respectively. We are also given the net value we need to achieve for each person.
With respect to above example, suppose A needs net value of 9, B needs net value of 16 and C needs net value of 25. So ideally A would require 3 objects, B would need 4 and C would need 5. But the number of objects are limited. So, we need to distribute the objects in such a way that the maximum deficiency of required value among all people is minimum possible.
According to given example, if we have only 2 objects, both of them would go to person C, then the maximum deficiency would be 16(person B) which is minimum possible. Similarly if we have 3 objects, 2 would go to C and one would go to A, and maximum deficiency would be 15(person C).
So, summing up the entire thing:
We are given the net requirements of all the persons and the value of object for each person as well. We need to find the minimum possible value of maximum deficiency.
Input format
3 2 (Number of people space number of objects)
9 16 25 (net requirements of each)
3 4 5 (value of object for each)
Output
16 (explained above)
The value of N(number of objects is very high, upto 10^18) So I can't do it in O(N), but the number of people is max 10^5. Is there any way we can think of a solution which takes O(M) or O(MlogM) time.