I’m still not sure if your algorithm is correct for this version of the problem. We can only drop cows where haybales are, and what your algorithm does is drop a cow so that it just reaches the leftmost unexploded bale.
I did not see such requirement, and it passed the USACO online judge.
we’re talking about a modified version of the problem here…
I have a O(n\lg^2 n) solution with your adjusted problem.
First do binary search, then do dynamic programming.
let \text{dp}[i] be the minimal amount of cows needed to make 1-i covered.
then we binary search l and r, which is the first element of x[] out of the [x[i]-mid,x[i]+mid].
Then \text{dp}[k] = min(\text{dp}[k],\text{dp}[l]+1) \text{ where [l<k<r]}
This can be optimized into O(n \lg n) using segment tree. Considering the binary search that we did initially, the time complexity is O(n\lg^2 n)
The dp is a range minimum where the left endpoint moves monotonically right, which can be done in O(N) time with a deque.
But you can notice that you don’t even need a range minimum, since the dp table is monotonically increasing (if you define it to be dp[i] = covering at least cows 1 through i). So it can be done with two pointers in O(n), more or less equivalent to the greedy solution.