P3853 [TJOI2007] Road Sign Placement

There is a long highway between city B and city T. Some places along this highway have signposts, but everyone feels there are too few; adjacent signposts are often separated by a rather long distance. To study this problem, we define the maximum distance between adjacent signposts on the highway as the highway’s "emptiness index".

Now the government plans to add some signposts on the highway to minimize the highway’s "emptiness index". They ask you to design a program to compute the minimum achievable value. Note that the start and the end of the highway are guaranteed to already have signposts, the highway length is an integer, and both existing and newly added signposts must be at integer distances from the start.

The first line contains three integers $L,N,K$, representing the highway length, the number of existing signposts, and the maximum number of signposts that can be added, respectively. The second line contains $N$ integers in increasing order, representing the positions of the existing $N$ signposts. Each position is the distance from the start and lies within the interval $[0,L]$.

Output one line containing a single integer, the minimum "emptiness index" achievable after adding signposts.

Originally, the highway had only two signposts at the start and the end. Now you are allowed to add one signpost. You should place the new signpost at a distance of $50$ or $51$ from the start, which yields the minimum emptiness index of $51$. Constraints: - In $50\%$ of the testdata, $2 \leq N \leq 100$, $0 \leq K \leq 100$. - In $100\%$ of the testdata, $2 \leq N \leq 100000$, $0 \leq K \leq 100000$. - In $100\%$ of the testdata, $0 < L \leq 10000000$. Translated by ChatGPT 5