三分法

洛谷P3382

题目描述

如题,给出一个$n$次函数,保证在范围$[l,r]$内存在一点$x$,使得$[l,x]$上单调增,$[x,r]$上单调减。试求出$x$的值。

样例:

Input:

3 -0.9981 0.5
1 -3 -3 1

Output:

-0.41421

样例简析:

对于样例数据,$n=2,l=-0.9981,r=0.5$且$y=x^3-3x^2-3x+1$

img

如图,红色段即为该函数$f(x)=x^3-3x^2-3x+1$在区间$[-0.9981,0.5]$内的图像

当$x=-0.41421$时$f(x)$在$x∈[l,r]$上取到最大值,

所以当$x=-0.41421$,$f(x)$在$[l,x]$上单调增,$[x,r]$上单调减。

分析

因为题目保证在范围$[l,r]$内存在一点$x$,使得$f(x)$在$[l,x]$上单调增,$[x,r]$上单调减。

所以$f(x)$在$[l,r]$上有一单峰。

求单峰函数(可不严格递增递减,即$[l,r]$中间可能有$f(x_1)=f(x_2)$)的峰值,可以用三分法:

  1. $f(l+(r-l)/3)>f(r-(r-l)/3)$,则$x$不可能在$[r-(r-l)/3,r]$那么此时$r=r-(r-l)/3$
  2. $f(l+(r-l)/3)≤f(r-(r-l)/3)$,则$x$不可能在$[l,l+(r-l)/3]$那么此时$l=l+(r-l)/3$。

递归即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstring>
#include<iostream>
#include <iomanip>
using namespace std;
int n;
long double l,r,ml,mr,xs[15];
inline long double f(long double x)
{
register int i,j;
register long double ret=0,px=1;
for(i=n;i>-1;--i,px=1)
{
for(j=1;j<=i;++j)
px*=x;
ret+=px*xs[i];
}
return ret;
}
int main()
{
register int i;
ios_base::sync_with_stdio(0);
cin>>n>>l>>r;
for(i=n;i>-1;--i)cin>>xs[i];
while(r-l>=1e-9)
{
//ml=l+(r-l)/3.0;mr=r-(r-l)/3.0;
ml=(r+2.0*l)/3.0;mr=(2.0*r+l)/3.0;
//据说这样更快。。。
if(f(ml)>f(mr))r=mr;
else l=ml;
}
cout<<fixed<<setprecision(5)<<l<<endl;
return 0;
}