本文主要是介绍[ACM] CSU 1548 Design road （三分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.csu.edu.cn/OnlineJudge/problem.php?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;
}
这篇关于[ACM] CSU 1548 Design road （三分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
