三分算法

三分算法

用于计算单峰函数求极值

Party All the Time HDU - 4355 浮点数三分算法 模板

//浮点三分 const double EPS = 1e-9; while(r - l > EPS) { double lmid = l + (r - l) / 3; double rmid = r - (r - l) / 3; lans = f(lmid),rans = f(rmid); // 求凹函数的极小值 if(lans <= rans) r = rmid; else l = lmid; // 求凸函数的极大值 if(lans >= rans) l = lmid; else r = rmid; } // 输出 l 或 r 都可 cout << l << endl;

AC代码

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; const double EPS=1e-5; const int maxn=5e4+100; int n; struct node { double weizhi,weight; }a[maxn]; inline double trible(double x) { return x*x*x; } double f(double x) { double add=0; for(int i=1;i<=n;++i) add+=trible(fabs(x-a[i].weizhi))*a[i].weight; return add; } int main(void) { int t,cnt=0; cin>>t; while(t--) { scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%lf %lf",&a[i].weizhi,&a[i].weight); double l=a[1].weizhi,r=a[n].weizhi; while(r-l>EPS) { double midl=l+(r-l)/3; double midr=r-(r-l)/3; if(f(midl)>=f(midr)) l=midl; else r=midr; } printf("Case #%d: %d\n",++cnt,(int)floor(f(l)+0.5)); } return 0;//小卜世界第一可爱 }

Restorer Distance CodeForces - 1355E 整数型三分算法 模板

//整数三分 int l = 1,r = 100; while(l < r) { int lmid = l + (r - l) / 3; int rmid = r - (r - l) / 3; lans = f(lmid),rans = f(rmid); // 求凹函数的极小值 if(lans <= rans) r = rmid - 1; else l = lmid + 1; // 求凸函数的极大值 if(lasn >= rans) l = lmid + 1; else r = rmid - 1; } // 求凹函数的极小值 cout << min(lans,rans) << endl; // 求凸函数的极大值 cout << max(lans,rans) << endl;

AC代码

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; const int maxn=2e5+100; ll N,A,R,M,l,r,ans=INF,a[maxn]; ll f(ll h) { ll ans=0,sub=0,add=0; for(int i=1;i<=N;++i) if(a[i]>h) sub+=a[i]-h; else add+=h-a[i]; if(M<A+R) { ll change=min(add,sub); ll cha=add-sub; ans+=change*M; if(cha>0) ans+=cha*A; else ans-=cha*R; } else ans=sub*R+add*A; return ans; } int main(void) { scanf("%lld %lld %lld %lld",&N,&A,&R,&M); M=min(M,A+R); for(int i=1;i<=N;++i) { scanf("%lld",&a[i]); r=max(r,a[i]); } sort(a+1,a+1+N); while(l<r) { ll midl=l+(r-l)/3; ll midr=r-(r-l)/3; if(f(midl)>=f(midr)) l=midl+1; else r=midr-1; } printf("%lld",f(l)); return 0;//小卜世界第一可爱 }