首先來說說三分的概念：

?

二分是把區間分為長度相等的兩段，三分則是把區間分為長度相等的三段，進行查找，這樣的查找稱為三分查找，三分查找通 ? 常用來迅速確定最值。 ? 眾所周知，二分算法的要求是搜索的序列是單調序列，而三分法所面向的搜索序列的要求是：序列為一個凸性函數。 ? ? ? 與二分法類似，三分算法先把區間分為長度相等的三段，那么l與r之間就有兩個點，分別是：ll=l+(r-l)/3=(2l+r)/3和 ?rr=r-(r-l)/3=(l+2r)/3 ? 如果ll比rr更靠近最值，我們就舍棄右區間，否則我們舍棄左區間。 ? ? 算法的正確性： 1、ll與rr在最值的同一側。由于凸性函數在最大值（最小值）任意一側都具有單調性，因此，ll與rr中，更大 （小）的那個數自然更為靠近最值。此時，我們遠離最值的那個區間不可能包含最值，因此可以舍棄。 2、ll與rr在最值的兩側。由于最值在中間的一個區間，因此我們舍棄一個區間后，并不會影響到最值。 ? ? 典型題目：HDU4355,HDU2438，POJ3301 ? ? 題目：Party All the Time #include <iostream> #include <string.h> #include <stdio.h> #include <math.h>using namespace std;const double EPS=1e-4; const int N=50010;double p[N],w[N]; int n;double equ(double x) {double ans=0;for(int i=0;i<n;i++){double S=fabs(p[i]-x);ans+=w[i]*S*S*S;}return ans; }double ternarySearch(double l,double r) {while(r-l>EPS){double ll=(2*l+r)/3;double rr=(l+2*r)/3;double ans1=equ(ll);double ans2=equ(rr);if(ans1>ans2)l=ll;elser=rr;}return l; }int main() {int T,i;scanf("%d",&T);for(int t=1;t<=T;t++){scanf("%d",&n);double l=1000000;double r=-1000000;for(i=0;i<n;i++){scanf("%lf%lf",&p[i],&w[i]);if(p[i]<l) l=p[i];if(p[i]>r) r=p[i];}double tmp=ternarySearch(l,r);printf("Case #%d: %.0lf\n",t,equ(tmp));}return 0; } 題目：Turn the corner 題意：給定一個直角彎道的兩條道路的寬度，然后再給出汽車的長度與寬度，問汽車能否通過該彎道？ ? 如下圖： 要使汽車能轉過此彎道，那么就是汽車的左邊盡量貼著那個直角點，而汽車的右下后方的點盡量貼著最下面的邊。 我們以O點為原點建立直角坐標系，我們可以根據角a給出P點橫坐標的函數F(a) ? 那么很容易得到： 其中有條件：，可以很容易證明是一個單峰函數，所以接下來就是三分了，如果的最大值小于等于 ? y，那么就能通過此直角彎道，否則就通不過。 ? #include <iostream> #include <string.h> #include <stdio.h> #include <math.h>using namespace std;const double EPS=1e-8; double x,y,l,w;double equ(double t) {return l*cos(t)+(w-x*cos(t))/sin(t); }double ternarySearch(double l,double r) {while(r-l>EPS){double ll=(2*l+r)/3;double rr=(l+2*r)/3;double ans1=equ(ll);double ans2=equ(rr);if(ans1<ans2)l=ll;elser=rr;}return l; }int main() {while(~scanf("%lf%lf%lf%lf",&x,&y,&l,&w)){double low=0,high=acos(-1.0)/2;double tmp=ternarySearch(low,high);if(equ(tmp)<=y) puts("yes");else puts("no");}return 0; }
? 題目：Texas Trip 題意：平面上給定n個點的坐標，求出包含這n個點的最小的正方形的面積。 ? 分析：我們先找出一個邊長都平行于坐標軸的最小的正方形，然后我們只需要在0到90度的所有點旋轉過程中，每次旋轉一點就 比較，然后記錄邊長最小的正方形，而在這個旋轉過程中正方形的邊長關于旋轉角度的函數是一個單峰函數，所以可以三分。 ? 這里要知道坐標旋轉公式： 如果為旋轉前的坐標，為旋轉后的坐標，那么有： ? ? #include <iostream> #include <string.h> #include <stdio.h> #include <math.h>using namespace std;const double EPS=1e-12; const double PI=acos(-1.0); const double INF=1e6; const int N=35;double x[N],y[N]; int n;double Tri(double t) {double tx,ty;double bx,by,sx,sy;bx=by=-INF;sx=sy=INF;for(int i=0; i<n; i++){tx=x[i]*cos(t)-y[i]*sin(t);ty=x[i]*sin(t)+y[i]*cos(t);//旋轉坐標系，求出旋轉后的點應該在什么位置bx=max(tx,bx);sx=min(tx,sx);by=max(ty,by);sy=min(ty,sy);}return max(bx-sx,by-sy);}double ternarySearch(double l,double r) {while(r-l>EPS){double ll=(2*l+r)/3;double rr=(l+2*r)/3;double ans1=Tri(ll);double ans2=Tri(rr);if(ans1>ans2)l=ll;elser=rr;}return l; }int main() {int t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%lf%lf",&x[i],&y[i]);double low=0,high=PI/2;double tmp=ternarySearch(low,high);printf("%.2lf\n",Tri(tmp)*Tri(tmp));}return 0; }

總結

以上是生活随笔為你收集整理的三分搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。