RT,之前在模拟赛上遇到求单峰单谷函数的极值,由于不会(不熟悉)三分然后手搓了下面这个写法:
n=rd();for(int i=1;i<=n;i++)a[i]=rd(),b[i]=rd(),c[i]=rd();
double l=0,r=1000,mid;
while(l+eps<=r)
{
mid=(l+r)/2;
if(f(mid-eps)>f(mid)&&f(mid)>f(mid+eps))l=mid+eps;
else r=mid-eps;
}
printf("%.4lf\n",f(mid));
一直到现在我都是用的这种写法求上述问题。想问一下这种方法与常规的三分写法的优劣之处,以及这种写法是否可以代替三分。理论上这种写法每次二分多判了一次,所以相比较三分常数会增加 21(当然上面的实现常数增加了一倍,但是显然可以做到这个常数),但是相较于底数又从 23 变成了 2,理论上是会跑的更快,经过实测,在二分写法下比三分写法下的速度要快 41。二分写法,三分写法。