I am trying to solve this problem: http://acm.tju.edu.cn/toj/showp2886.html
I tried several solutions, I will explain 2 of them. Note that both assume that the cost (position) is a convex function, which means that it decreases towards the middle (in fact, it is somewhere in the direction of the median (supply point)), and the graph is more or less similar to U- shaped shape.
Finding the left and right position of the supply point, which has a cost (position) <= M. After I find the minimum and maximum value, I try to see if I can make the interval a little longer (since the restaurant does not have to be places at the point of delivery). This is a good solution, but it is very important to calculate the last bit. It fails in tests where M is very large, and there are several supply points at minimal cost. Difficulty: O (NlogN) + O (M). This solution is lower, because it gets the time limit exceeded, but I tried another one, where I calculate in O (1) how much I can go in both directions, and get the wrong answer.
Since the function is convex, I can use triple search to find the minimum value. If the minimum is less than M, I then binary search for the lower and upper bounds (which means M) of the function. Difficulty: O (NlogM), because for each O (logM) I calculate the cost in O (N).
This is what I tried, and I still get the "Wrong answer", so I need help, as it makes me go out.
The problem is not entirely clear in the specifications (or, at least, I think so), because when I first read it, I did not think that the cost was calculated from all supply points, but only from the nearest one. An example cleared this. In addition, I do not know if my assumption that the cost (position) function is convex is really true. But I have tried many examples, and it seems like that.
Thank. Any help appreciated .: D