欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P3382 【模板】三分法,难度⭐⭐⭐

程序员文章站 2022-07-13 13:52:56
...

P3382 【模板】三分法
P3382 【模板】三分法,难度⭐⭐⭐

法1 : 三分法

对于一个二次函数[L,R]内取最值,选取两个点x=(2∗l+r)/3,y=(l+2∗r)/3

若f(x)>f(y),那么[y,R]这一段可以舍弃(一定不会成为最优解),否则[l,x]这一段舍弃

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)

using namespace std;
typedef long long ll;//全用ll可能会MLE,ll比int占的内存大

const ll N=1000007;
const ll INF=1e9+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;
#undef mid

ll n;
double a[20],l,r;

inline double f(double x)
{
    double ans=0;
    lver(i,n,0)
    ans=ans*x+a[i];
    return ans;
}

int main()
{
    scanf("%lld %lf %lf",&n,&l,&r);
    lver(i,n,0)scanf("%lf",&a[i]);
    while(l+EPS<r)
    {
        double x=(2*l+r)/3;
        double y=(2*r+l)/3;
        if(f(x)>f(y))r=y;
        else l=x;
    }
    printf("%.5f\n",l);
    return 0;
}

法2 : 求导+二分

膜鱼%%%
P3382 【模板】三分法,难度⭐⭐⭐

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)

using namespace std;
typedef long long ll;//全用ll可能会MLE,ll比int占的内存大

const ll N=1000007;
const ll INF=1e9+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi= 3.141592653589793238462643383279;
#undef mid

ll n,m;
double a[N];
double l,r;

//秦九韶公式求多项式
inline double f(double x)
{
    double u[20];
    u[n]=a[n];
    lver(i,n-1,0)
    u[i]=u[i+1]*x+a[i];//其实就是按照x的次数乘
    return u[0];
}

inline double check(double x)
{
    double dx=EPS;
    double dy=f(x+dx)-f(x);
    return dy/dx;
}
int main()
{
    scanf("%lld",&n);
    scanf("%lf%lf",&l,&r);
    over(i,0,n)
    scanf("%lf",&a[n-i]);
    double mid;
    while(l+EPS<r)
    {
        mid=(l+r)/2;
        if(check(mid)>0)l=mid;
        else r=mid;
    }
    printf("%.5f",mid);
    return 0;
}

注:如果您通过本文,有(qi)用(guai)的知识增加了,请您点个赞再离开,如果不嫌弃的话,点个关注再走吧 ! 当然,也欢迎在讨论区指出此文的不足处,作者会及时对文章加以修正 !