算法思想-三分

本文主要是介绍算法思想-三分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

我认为三分就是就是关于二分的延伸思想，二分用于求解线性的相关问题，三分用于求解单谷凹凸函数的最值问题。
首先简述一下三分
三分思想用于解决一类求解函数的极值的方法（单谷凹凸函数）
有多种创建三分的方法，第一种相对来说更常用，其他的理解想法就行了。他们都是通过两者的值相比较，取其中一方，让 r 或 l 的值移动，进行区间缩小，找到函数顶点
这是第一种创建三分的方法

int ml = l + (r-l)/3;
int mr = r + 2*(r-l)/3;
if(f(ml) > f(mr) l = ml;//上图所示，应该偏向右边才是顶点
else r = mr;

第二种方式

int mid = (l+r)/2;
int midmid = mid + (mid+r)/2;
if(f(mid) > f(midmid)) l = mid;
else r = midmid;

第三种

在二分的很小的范围内找到一个 mid + eps 的点，判断它和 mid 值的大小，这种思路类似于二分，但是思想还是三分，可以自己理解一下。

double eps = -1e18;//表示趋向mid点很小的点，判断两点之间的大小关系就可以
int mid = (l+r)/2;
if(f(mid - eps) > f(mid)) l = mid-eps;
else r = mid;

然后就是用总体的来写出

int l = 0,r = 1e18;	//范围的值，我们从0到1e18
for(int i = 1;i <= 300;i++){
	int ml = l + (l+r)/3;
	int mr = l + 2*(l+r)/3;
	if(f(ml) > f(mr)) l = ml;	//f()函数就是你现在要求的内容，就是将问题转化成凹函数的内容
	else r = mr;
}

例题：
1.hdu 4355
题意：给你数轴上n个点的坐标还有他们的权重 w，让你找一个点，是这个点的距离到其他点的距离三次方再乘上位权的最小。

思路：简单理解一下，一个点到其他点的距离之和最小，那么就先要确定这个点的能取得位置，简单想象一下，这个点取最左边，是不是这个距离之和就非常大。这个点取最右边，同理这个点是不是也非常的大。当可以去的点左右两边同时向中间走的时候，总距离是不是就减小，直到中间可能有一个点取得最小值。具体证明就不用证了。可以将问题转化成用三分求凹函数求最值的问题。

参考代码

2.hdu 3400
题意：在一个二维平面内给定你两条传送带线段，AB和CD。然后在AB传送带上的速度是P，在CD传送带上的速度是Q，在平面其他部分的速度是R，问你从A到D点花费最短的时间是多少？

思路：我们要从A到D，是需要先从AB上的某个位置E离开，然后走中间的路线，最后到达CD上的某一点F，最后通过CD到达D点（当然AB和CD这两部分可以不走）

为什么要这样考虑呢？
因为 |AE|P/+|EF|/R 的值可能小于直接走 |AF|/R 的值。
另 g = |AE|P/+|EF|/R
所以我们先固定点 F，开始考虑从 A 到 F 的最短距离是在哪个点 E
很明显，我们固定 F 点以后，我们让 E 点从 A 到 B ，路径值 g 是先减小后增大的一个关系
再另 f = |FD|/Q
这是否让 F 的位置改变，FD的大小是一个递减函数，结合 g 值，f + g 总体是一个先减后增的函数，然后就可以使用三分找最值。

参考代码

3.buctoj周赛（5）逃离
三分的题目一般都是思维题目，只要能将问题转化为三分就好解决，这个题目转化上相对不好理解一些，可以参考学习一下

4.Turn the Corner

汽车拐弯问题，给定 X,Y,l,d 值当你考虑完过后，你会很容易想到，汽车拐弯无非是向前走（最上面的点不能超过墙），或者是在墙角的点转动（最左边的点不能超过墙），最后其实只要考虑最上面的点就行了。因为每当绕墙转动（随着角度变化改变），最左边的点碰到墙时，你就可以让车向前走，相应的增加的是最大高度 h 的值，所以总体来看你只需考虑最大高度 h 即可。
我们模拟发现，h 的值是先增大后减小的，所以可以看成一个凸函数，找最大值就可以了。
关键是找出 h 的函数：

s = l*cos(θ) + w*sin(θ) - x;
h = s*tan(θ) + w*cos(θ);	//θ 就是0 - pi/4

代码参考链接

总体来说，三分的内容与二分相似，大多结合思维题，就是将问题的模型转变成三分比较困难,如果能转化问题就迎刃而解了

这篇关于算法思想-三分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！