求问三分
  • 板块P1883 函数
  • 楼主_Day_Tao_
  • 当前回复20
  • 已保存回复20
  • 发布时间2024/10/22 17:37
  • 上次更新2024/10/22 19:57:18
查看原帖
求问三分
1247131
_Day_Tao_楼主2024/10/22 17:37

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));

一直到现在我都是用的这种写法求上述问题。想问一下这种方法与常规的三分写法的优劣之处,以及这种写法是否可以代替三分。理论上这种写法每次二分多判了一次,所以相比较三分常数会增加 12\frac{1}{2}(当然上面的实现常数增加了一倍,但是显然可以做到这个常数),但是相较于底数又从 32\frac{3}{2} 变成了 22,理论上是会跑的更快,经过实测,在二分写法下比三分写法下的速度要快 14\frac{1}{4}二分写法三分写法

2024/10/22 17:37
加载中...