Suppose that we ask a different question. Say that we need the shortest distance between any two rocks to be at least W, and we want to know how many rocks we have to remove. If the answer to this is R(W), and R(W) <= M (where M is the number of rocks that we're allowed to remove in the original problem) then we know that the answer to the original problem is at least W, since we've just demonstrate a solution.
So we require that the distance between any two consecutive rocks is at least W. We walk through the rocks left to right, greedily counting how many rocks we will have to remove. For each rock, if its distance from the last rock that we've kept is at least W, then we keep this rock. If not, then we remove this rock.
We claim that this will give us the best solution. Say that we have the best solution for the first K rocks and are considering adding the K+1-st rock. If we can just add the K+1-st rock, we do. If it's too close to the previous rock, then a solution including the K+1-st rock could not include the previous rock. But, since we already had the best solution for all of the rocks before that one, we couldn't have any more rocks earlier in the river. Thus, we just add a rock and subtract a rock, and don't do any better.
Now, since we can figure out, for each W, if our answer is at least W, we can do binary search to find the answer. We start with A=0 and B=L. A will always be less or equal to the answer, and B will always be greater than or equal to the answer. While A and B are different, we pick a number C halfway between A and B. If we can do W=C, we know that the answer is at least C, so we set A=C. Otherwise, we set B=C-1. When we get A=B, we're done, and we know that that's our answer.
#include <stdlib.h> #include <stdio.h> const int MAXROCKS = 200000; int len, rocks, r; int rock[MAXROCKS]; int intcmp(const void *p1, const void *p2){ return(*(int*)p1 - *(int*)p2); } int main(){ FILE* fin = fopen("jump.in", "r"); fscanf(fin, "%d %d %d", &len, &rocks, &r); for(int i = 0; i < rocks; ++i){ fscanf(fin, "%d", &rock[i]); } fclose(fin); qsort(rock, rocks, sizeof(int), intcmp); int a = 0; int b = len; while(a < b){ int c = (a + b + 1) / 2; int p = 0; int hits = 0; for(int i = 0; i < rocks; ++i){ if(rock[i] - p < c){ ++hits; } else { p = rock[i]; } } if(hits > r){ b = c-1; } else { a = c; } } FILE *fout = fopen("jump.out", "w"); fprintf(fout, "%d\n", a); fclose(fout); return(0); }