Minimization of the maximum element in an array

Question

You have an array of size n of positive integers on which you can do the following operation by at most N times:

• Choose a sub-array and decrease its elements value by k (k must be smaller than the sub-array's minimum value).
• Such an operation costs the size of the sub-array multiplied by k.
• The total costs of these operations must not be larger than M.
• N and M can be extremely large.

Can you give me an efficient algorithm for minimizing the maximum element in this array?

Answer 1

Suppose we chose x as the maximal number in the reduced array we can take the array and decrease all its larger elements to x and calculate the cost of these operations and their number then we can try joining greedily the cheapest(in cost) subsets of these elements until the number of operations is smaller than N.If cost becomes larger than M then the maximal element must be larger in the reduced array.As for x we can easily binary search it.