P3382 【模板】三分法

文章目录

R e s u l t Result Result

---

H y p e r l i n k Hyperlink Hyperlink

https://www.luogu.com.cn/problem/P3382

---

D e s c r i p t i o n Description Description

给定一个 n n n次函数的各此项次数，求该函数在 [ L , R ] [L,R] [L,R]上的单峰

数据范围： 7 ≤ n ≤ 13 7\leq n\leq 13 7≤n≤13

---

S o l u t i o n Solution Solution

解法一：
定义法，单峰的定义是在峰前单调递增，峰后单调递增
那么我们找到一个 m i d mid mid判断它的左边一点点和右边一点点的大小关系，从而判断它的增减性，来改变区间
解法二：
求导法，容易知道，峰前的斜率为正，峰顶为0，峰后为负，可以以此为依据二分

注意用秦九韶算法 O ( n ) O(n) O(n)求函数值

时间复杂度： O ( n log ⁡ n ) O(n\log n) O(nlogn)

---

C o d e Code Code

#include<cstdio>
#include<cmath>
using namespace std;int n;
const double eps=1e-7;
double a[20],L,R,mid;
inline double f(double x){double s=0;for(register int i=n;i>=0;i--) s=s*x+a[i];return s;}
signed main()
{
	scanf("%d%lf%lf",&n,&L,&R);
	for(register int i=0;i<=n;i++) scanf("%lf",&a[n-i]);
	while(fabs(L-R)>=eps)
	{
		mid=(L+R)/2.0;
		if(f(mid+eps)>f(mid-eps)) L=mid;else R=mid;
	}
	printf("%.5lf",R);
}

#include<cstdio>
#include<cmath>
using namespace std;int n;
const double eps=1e-7;
double a[20],L,R,mid;
inline double f(double x){double s=0;for(register int i=n;i>=0;i--) s=s*x+a[i];return s;}
inline double slope(double x){return (f(x+eps)-f(x))/eps;}
signed main()
{
	scanf("%d%lf%lf",&n,&L,&R);
	for(register int i=0;i<=n;i++) scanf("%lf",&a[n-i]);
	while(fabs(L-R)>=eps)
	{
		mid=(L+R)/2.0;
		if(slope(mid)>0) L=mid;else R=mid;
	}
	printf("%.5lf",mid);
}