HDU3400 三分查找

题目大意

HDU3400.在二维平面上有两条线段AB、CD。AB上的速度是P,CD上是Q,平面上的其他区域上速度为R。求A->D的最少时间。


思路

由于我们必须在A出发,在D结束,所以我们必然会在两条线段上行走一段距离。而知道在这两条线段上分别应当走多少距离,就是这道题的关键。我们设点q,p分别是在AB CD上的两个点,暴力枚举这两个点的位置(即距离A、D的距离)显然是不行的。而面对求一个极值(在这题里是最短时间)的问题二分也不适用,于是我们就有了三分查找。


三分简介

三分查找与二分相似。从名字就可以看出,三分的每次操作就是用两个点把当前的区间分成三个区间。即在二分查找的基础上,在右区间(或左区间)再进行一次二分。该算法通常用来迅速确定最值。二分查找所面向的搜索序列的要求是:具有单调性。而三分查找所面向的搜索序列的要求是:序列为一个凸性函数。即该序列必须有一个最大值(或最小值),在极值的左侧序列,必须满足不严格单调递增(递减),右侧序列必须满足不严格单调递减(递增)。如下图,表示一个有最大值的凸性函数:

    

算法流程

(1)与二分法类似,先取整个区间的中间值mid。

 

(2)再取右侧区间的中间值midmid,从而把区间分为三个小区间。

(3)如果mid比midmid更靠近最值,我们就舍弃右区间,否则我们舍弃左区间。

比较mid与midmid谁最靠近最值,只需要确定mid所在的函数值与midmid所在的函数值的大小。当最值为最大值时,mid与midmid中较大的那个自然更为靠近最值。最值为最小值时同理。

(4)重复(1)(2)(3)直至找到最值。

代码

挖个坑以后再填(逃)

总结

因为大多数题不用单独写judge函数,所以总体上看三分比二分更水。但是每个算法都有它的必要性,三分也是如此。(众:这就是你又水了一贴的理由?)

发表评论

电子邮件地址不会被公开。 必填项已用*标注