首先放上队友的博客
看到最小最大值第一反应是二分,但是不明白怎么二分,看了队友的博客,以下胡言乱语全是根据队友博客的自己理解
首先我们的目标是errorF最小,设该最大误差是x,那么对于每个点,其误差都要小于x
现在我们考虑两个点,,若它们处于分段函数同一段上,即他们的都是是
若都小于,则要求
若都大于,则要求。
若,则同时要求,
我们的问题是什么情况下不能放在同一段呢?
这里需要想明白的一点是:考虑不适合放在同一段的时候,直接讨论第三种情况。
因为前两种情况,误差都会大于,要控制误差小于x,即<误差<x,对x的要求就会比第三种情况要大
不适合放在同一段的情况:直接距离差的太大了,大于2*x的时候,就无法满足他们的函数值相同且误差小于x了
我们这样想象,在线段之间插入线段,使得到它们都不超过x,当时,无论放在哪,距离小于x必然意味着距离大于x,反之同理。
据说画图更易理解,厚颜无耻地贴个丑图_(:з」∠)_
接下来就是要利用二分,二分有点求什么设什么的意思在里面。
设最小误差是x,按照v从小到大排序的时候,我们首先可以得到一个下界==,遍历后面的点去更新,,当出现时,属于分段函数同一段的点就被找完了,然后继续往后找,如果能找到三段区间,那么x可以更小一点,若不能找到三段区间,说明x太大了,太多的点被分为同一段了
以上,分析完毕(*^▽^*)
代码中注意事项:
v=0的时候F是0,误差为l,误差最大最小值一定不小于l,它们的误差固定了,所以不需要考虑v=0的点
疲辽,等这周被虐完再写这道题代码