我们相距十万光年

晨露正葱茏,来日胜景定无穷

01/21
22:50
HDU

HDU 2899 Strange Function

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2899

题目的大意是给你一个函数f(x),让你在x∈[0,100]求一下函数的最小值。

观察一下题目给出的函数的方程,当x∈[0,100]时,很显然函数并不是单调的。那么我们就没法二分,但是对于不单调的函数,我们可以在一定的区间内用三分法求极值。

这里就顺便简单的提一下三分法的用法吧。当你要二分的函数并不是单调的,先增后减或先减后增时,二分法就挂了,此时需要用到三分法。

(1)先减后增有极小值。设区间端点为leftright,三分的端点为l_midr_midl_midr_mid要低,l_mid对应的函数值要小于r_mid函数值。则所求的极小值在区间[left,r_mid],反之在[l_mid, right]。剩下的就是和二分一样调整区间的的大小关系就行了。那么l_midr_mid的取值是多少?一个不错的选择是l_mid1/3,r_mid2/3。

(2)先增后减有极大值。设区间端点为leftright,三分的端点为l_midr_midl_midr_mid要低,l_mid对应的函数值要小于r_mid函数值,则所求的极小值在区间[l_mid,right],反之在[left,r_mid]。

那么,解决这道题,如下:

去网上搜了一波题解,似乎有一种做法是对原函数求导之后发现,其导函数在x∈[0,100]时是单调的。因此可以二分其导函数来反向求原函数的极值。