【模板】三分答案（2个）

发表于 | 分类于 | 本文总阅读量 次
字数统计: 418 字 | 阅读时长 ≈ 1 分钟

三分答案，可以用来求解凹函数或者凸函数的最值问题。

当然，此类问题也可以通过对该函数求导，转换成对于导函数的二分答案问题（不过有一些函数可能不太能求导？）

三分答案的原理是在l与r之间再取两个点lm与rm，将[l,r]区间分为三段，比较f(lm)与f(rm)的值。假设函数为凹函数求最小值，且f(lm)<f(rm)，那说明lm更加靠近最值点（当然左右不均衡，只是一种形象的说法），那也就说明rm一定在最值点的右边，r=rm。对于其他情况以及凸函数同理，就是基于这么一种思想，可以使得l与r不断向最值点逼近。主要是思想就是保证在缩小的过程中最值点一直在[l,r]当中。

这里记录了一下两个三分答案的模板（都是求凸函数的最大值，正好与上面相反，可以帮助加深理解，凹函数的同理，理解以后非常好写），第一个是整数的三分答案，第二个是浮点数的三分答案模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//整数三分答案
int lv, rv;
while (l < r)
{
    int lm = l + (r - l) / 3;
    int rm = r - (r - l) / 3;
    lv = f(lm);
    rv = f(rm);
    if (lv < rv)
        l = lm + 1;
    else
        r = rm - 1;
}
ans = max(lv, rv);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//浮点三分答案
double lv, rv;
while (r - l > eps)
{
    double lm = l + (r - l) / 3;
    double rm = r - (r - l) / 3;
    lv = f(lm);
    rv = f(rm);
    if (lv < rv)
        l = lm;
    else
        r = rm;
}
ans = max(lv, rv);//浮点数的话lv,rv都可以