[ACM] CSU 1548 Design road （三分）

?id=1548

第一次接触三分，题意和代码参考的网上的。

题意：修路：从(0,0)~(x,y)，n个数表示有第二行开始有n行表示有n条河，tx是河的起始位置，，ty是河的宽度，有水的地方要修桥，而x，y表示修路的端点，C1表示修路每米的花费，C2表示修桥每米的花费，问你最后花费的最少金额！

思路：先把有河的地方都和到一起，然后它的宽度就知道了，那么就把高度三分，找花费最小的点

这里三分求的是最小值。

三分法介绍

在区间内用两个mid将区间分成三份，这样的查找算法称为三分查找,也就是三分法，三分法常用于求解单峰函数的最值。

还有一种理解，即在二分查找的基础上，在左区间或者右区间上再进行一次二分。

三分与二分的区别

二分法适用于单调函数，而单峰函数用二分明显不太好了，对于有些单峰函数，可以求导后转化为单调函数，从而使用二分，然而很多情况求导是很麻烦的，这时就需要用到三分了。

const int inf=0x3f3f3f3f;int n;double x,y,c1,c2,sum,ans;const double eps=1e-8;double dis(double x1,double y1,double x2,double y2){return hypot(x1-x2,y1-y2);}void fen3(double l,double r)//求最小值{double mid1=l+(r-l)/3;double mid2=l+(r-l)*2/3;double s1=dis(0,0,sum,mid1)*c2+dis(sum,mid1,x,y)*c1;double s2=dis(0,0,sum,mid2)*c2+dis(sum,mid2,x,y)*c1;if(fabs(s1-s2)<eps){ans=s2;return;}if(s1>s2)fen3(mid1,r);elsefen3(l,mid2);}int main(){while(scanf("%d%lf%lf%lf%lf",&n,&x,&y,&c1,&c2)!=EOF){sum=0;for(int i=1;i<=n;i++){double tx,ty;scanf("%lf%lf",&tx,&ty);sum+=ty;}fen3(0,y);printf("%.2f\n",ans);}return 0;}

没有人会帮你一辈子，所以你要奋斗一生。