回复 @zhengtn03 :
有可能是这个问题,我现在感觉我的三分有可能是不完全对的，只是恰好数据水？但是答案都是十分接近的

第四组 x=654512559.5 时，r=34168.5
错的原因可能是r随x变化不是严格凸的？存在既不增也不减的情况？存在平行于x轴的情况?

第四组实在过不了，跟答案差了0.5.......怎么都调不过，怒cheat
官方题解：DP/贪心
One approach for solving this problem is by combining a left-to-right scan with a right-to-left scan (one could call each scan either greedy or an example of dynamic programming). We first run a greedy/DP algorithm from left to right to determine for each hay bale the minimum power with which it must explode in order to propagate all the way left. We then do the same from right to left, computing for each hay bale the minimum power with which it must explode in order to propagate all the way to the right. Finally, by scanning through the list of hay bales, we can use these two numbers to identify the best "crossover" point where we should set the initial explosion.
Here is Mark Gordon's remarkably concise solution. Note how he uses a couple of clever tricks -- for example to run the algorithm from right to left, he simply reverses the input, runs the left-to-right algorithm, then reverses the output so it appears in the forward direction. Note also how he multiplies all haybale locations by 2 initially so only integer math is required; this eliminates any possibility of rounding error from using floating point numbers. This is why, for example, Mark uses "2 + max(..." in his final loop, since it would normally be "1 +" but the numbers are still scaled up by 2.
我的做法：三分奶牛的位置，二分爆炸半径
原因：我们不妨设某个位置最小的爆炸半径为R=F(X),X为位置，我们通过调试发现，F(X)是一个单峰函数（先减小后增大）
于是可以三分奶牛的位置，
我们又发现，R半径越大肯定“越能全部爆炸”，所以我们对于三分给出的位置，可以二分找出最小的爆炸半径，找出离这个位置最近的两个干草堆（我用的是对原数组排序后二分查找，set也可以）向左右两个方向模拟“爆炸”，注意当半径衰减为0或者没有新的草堆爆炸时要立即跳出（这是一个巨大的常数优化），再加上诸多的不合法状态，这样check(X,R)的复杂度就比O(n)小很多，就能水过这道题了
我跑得快的一个上面有注释
设最大的干草堆为M
我的复杂度最坏为O(n*log2(M)*2log3(M))
但是O(n)的这个因子实际上远远达不到，所以能写过