洛谷 P3382 【模板】三分法(三分二分)

2019-11-14 09:33:34

字體：大中小

來源：轉載

供稿：網友

P3382 【模板】三分法題目提供者HansBug 難度 普及/提高- 題目描述如題，給出一個N次函數，保證在范圍[l,r]內存在一點x，使得[l,x]上單調增，[x,r]上單調減。試求出x的值。這里寫圖片描述輸入輸出格式輸入格式：第一行一次包含一個正整數N和兩個實數l、r，含義如題目描述所示。第二行包含N+1個實數，從高到低依次表示該N次函數各項的系數。輸出格式：輸出為一行，包含一個實數，即為x的值。四舍五入保留5位小數。輸入輸出樣例輸入樣例#1： 3 -0.9981 0.5 1 -3 -3 1 輸出樣例#1： -0.41421 說明時空限制：50ms,128M 數據規模：對于100%的數據：7<=N<=13 樣例說明：如圖所示，紅色段即為該函數f(x)=x^3-3x^2-3x+1在區間[-0.9981,0.5]上的圖像。當x=-0.41421時圖像位于最高點，故此時函數在[l,x]上單調增，[x,r]上單調減，故x=-0.41421，輸出-0.41421。

/*三分答案做法.又學了一種三分答案姿勢.mid=(2*l+r)/3,midmid=(l+2*r)/3.常數要小很多...(并不會證明).*/#include<cstdio>#define MAXN 101#define eps 1e-7using namespace std;double a[MAXN],ans,l,r;int n;double check(double x){ double sum=0; for(int i=1;i<=n;i++) { double tot=a[i]; for(int j=1;j<=n-i;j++) tot*=x; sum+=tot; } return sum;}void sanfen(){ double mid,midmid; while(l+eps<r) { //mid=(l+r)/2,midmid=(mid+r)/2; mid=(2*l+r)/3,midmid=(l+2*r)/3; if(check(mid)>=check(midmid)) r=midmid,ans=mid; else l=mid; }