解决先单增，再单减的问题。

P3382 【模板】三分法

三分可以标准三分，也可以近似三分

标准三分：mid1，mid2为三等分点，一步一步跳

近似三分：mid为中点，跳mid-eps,mid+eps比较，理论上更快一些。

标准三分：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
typedef double db;
int n;
db a[N];
const db eps=1e-8;
db f(db x){
    db s=0;
    for(int i=n;i>=0;i--)s=s*x+a[i];
    return s;
}
int main(){
    db L,R;
    scanf("%d %lf %lf",&n,&L,&R);
    for(int i=n;i>=0;i--)scanf("%lf",&a[i]);
    while(R-L>eps){
        db k=(R-L)/3;
        db mid1=L+k,mid2=R-k;
        if(f(mid1)>f(mid2))R=mid2;
        else L=mid1;
    }
    printf("%.5lfn",L);
    // system("pause");
    return 0;
}

View Code

近似三分：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
typedef double db;
int n;
db a[N];
const db eps=1e-8;
db f(db x){
    db s=0;
    for(int i=n;i>=0;i--)s=s*x+a[i];
    return s;
}
int main(){
    db L,R;
    scanf("%d %lf %lf",&n,&L,&R);
    for(int i=n;i>=0;i--)scanf("%lf",&a[i]);
    while(R-L>eps){
        db mid=(R+L)/2;
        // db mid1=L+k,mid2=R-k;
        if(f(mid-eps)>f(mid+eps))R=mid;
        else L=mid;
    }
    printf("%.5lfn",L);
    // system("pause");
    return 0;
}

View Code

三分·三分求极值

HihoCoder - 1142

简单三分：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
typedef double db;
const db eps=1e-8;
struct point{db x,y;};
db a,b,c,sx,sy;
db dis(db x,db y){return sqrt((sx-x)*(sx-x)+(sy-y)*(sy-y));}
db f(db x){return a*x*x+b*x+c;}
int main(){
    scanf("%lf %lf %lf %lf %lf",&a,&b,&c,&sx,&sy);
    db Lx=-1e5,Rx=1e5;
    while(Rx-Lx>eps){
        // db mid=(Rx+Lx)/2;
        db k=(Rx-Lx)/3;
        db mid1=Lx+k,mid2=Rx-k;
        if(dis(mid1,f(mid1))>dis(mid2,f(mid2)))Lx=mid1;
        else Rx=mid2;
    }
    printf("%.3fn",dis(Lx,f(Lx)));
    // system("pause");
    return 0;
}

View Code

原文链接: https://www.cnblogs.com/littlerita/p/12591627.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/338613

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

三分法

P3382 【模板】三分法

三分·三分求极值

相关推荐