.

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

回复 @stdafx.h :
原本测试数据不知道被谁弄掉了，怎么搞

动态规划
代码详细见
为什么先卖货后进货，而不是先进货后卖货？
先进货后卖货10分，先卖货后进货100分？？

想传题，但并不想写评测插件......

快把2023弄好...好不容易写出来....

第四组实在过不了，跟答案差了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)的这个因子实际上远远达不到，所以能写过

回复 @liu_runda :
666666666666666666666那你还没上榜666666666666666666666666

orzorz

回复 @=_= :
233333，之前初始化不是0，后来忘删了

这波优化没做好...反而比预估慢了好多.....

orz

和773一模一样，重写昨天做的原题居然WA了一次。。

少了一个非常重要的hack：a=b=0。。

这道题的细节有毒

这题并没有约定p>n啊。。如果n=53，p=2该怎么做呢？不科学啊！

太神辣