三分法

二分法相信大家都会，它最基本的应用是求一个单调函数的零点。

三分法是二分法的变种，他最基本的用途是求单峰函数的极值点。

![[../../../images/Z-attachment/Pasted image 20231118201007.png]]

从数学的角度来说，求极值点，先求导再二分不就好了吗？然而，实际中我们遇到的函数，求导可能很困难，所以会用上三分法。而三分法的原理非常简单，以求极大值为例，每次对一个区间[l,r]求三等分点lsec和rsec：

• 如果f(lsec) < f(rsec) ，说明极大值一定在[lsec,r]内取到，因为如果在[0,lsec)内，那rsec一定处于单调下降的区间内，它的函数值不可能大于lsec的函数值。 于是我们令l=lsec并继续。

![[../../../images/Z-attachment/Pasted image 20231118201033.png]]

• 如果f(lsec) > f(rsec)，同理，极大值一定在[l,rsec]内取到，令r=rsec并继续。

![[../../../images/Z-attachment/Pasted image 20231118201050.png]]

这样进行下去，直到l和r的差距小于设定的eps为止。如果求的是极小值而非极大值，只需把上面条件判断处的大于、小于互换。

按照上面的算法，我们每次减少三分之一的长度。但其实还可以优化，即每次在中点附近取点，那么每次可以减少约二分之一的长度。

while (r - l > eps)
{
    mid = (l + r) / 2;
    double fl = f(mid - eps), fr = f(mid + eps);
    if (fl < fr)
        l = mid; // 这里不写成mid - eps，防止死循环；可能会错过极值，但在误差范围以内所以没关系
    else
        r = mid;
}

这种写法的三分，其实和普通的二分很像了。

1 三分套三分

以上是求一元单峰函数的极值的方法，如果是二元函数呢？可以三分套三分。例如，求函数 \(f(x,y)=(x-1)^2+(x+y)^2+\sin y\)在 \(-4\le x\le 4,-4\le y\le 4\) 时的极小值。

![[../../../images/Z-attachment/Pasted image 20231118201059.png]]

对于这个函数，无论固定 \(x\) ，还是固定 \(y\) ，都易证它是一个单峰函数。所以可以先三分一个变量，再固定这个变量，三分另一个变量，来求出最后的答案。

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
double f(double x, double y) {
    return (x - 1) * (x - 1) + (x + y) * (x + y) + sin(y);
}
double run(double x) // 固定x，三分y {
    double l = -4, r = 4, mid;
    while (r - l > eps)
    {
        mid = (l + r) / 2;
        if (f(x, mid - eps) > f(x, mid + eps))
            l = mid;
        else
            r = mid;
    }
    return f(x, mid);
}
int main() {
    double l = -4, r = 4, mid, ans;
    while (r - l > eps)
    {
        mid = (l + r) / 2; // 三分x
        if (run(mid - eps) > run(mid + eps))
            l = mid;
        else
            r = mid;
    }
    printf("%.6f\n", run(mid)); // -0.918827
    return 0;
}

[SCOI2010] 传送带这道题目就会用到三分套三分的方法，设 \(E\) 是 \(AB\) 上的点， \(F\)是 \(CD\) 上的点，那么最优路径应当是 \(A\rightarrow E\rightarrow F\rightarrow D\)，那么我们分别设出 \(AE\) 占 \(AB\) 的比例 \(x\) 和 \(DF\) 占 \(CD\) 的比例 \(y\) ，得到函数：

\(f(x,y)=\frac{x\cdot len(AB)}{P}+\frac{y\cdot len(CD)}{R}+\frac{len(EF)}{Q}\)

其中 \(len(E,F)\) 是一个关于 \(x,y\) 的函数，它显然对 \(x\) 和 \(y\) 而言都是单峰的（垂直时最小），再加上前面的单调函数，总体仍是单峰的，那么用三分套三分求解即可。

如果不会证明单峰性，其实可以写个程序打个表，目测一下正确性。

2 三分答案

和二分答案类似，也可以三分答案。例如：

You have to restore the wall. The wall consists of \(N\) pillars of bricks, the height of the \(i\) -th pillar is initially equal to \(h_i\), the height is measured in number of bricks. After the restoration all the \(N\) pillars should have equal heights.
You are allowed the following operations:
您可以进行以下操作：
● put a brick on top of one pillar, the cost of this operation is \(A\) ;
●在一根柱子上放一块砖，此操作的成本为 \(A\);
● remove a brick from the top of one non-empty pillar, the cost of this operation is \(R\) ;
●从一个非空支柱的顶部拆除一块砖，此操作的成本为 \(R\);
● move a brick from the top of one non-empty pillar to the top of another pillar, the cost of this operation is \(M\) .
●将一块砖从一个非空柱子的顶部移动到另一个柱子的顶部，此操作的成本为 \(M\) 。
You cannot create additional pillars or ignore some of pre-existing pillars even if their height becomes \(0\) .
您不能创建额外的支柱或忽略一些预先存在的支柱，即使它们的高度变为 。
What is the minimal total cost of restoration, in other words, what is the minimal total cost to make all the pillars of equal height?
修复的最小总成本是多少，换句话说，使所有柱子高度相等的最小总成本是多少？
Input
The first line of input contains four integers \(N,A,R,M\) \((1≤N≤10^5,0≤A,R,M≤10^4)\) — the number of pillars and the costs of operations.
输入的第一行包含四个整数 \(N,A,R,M\) - 支柱的数量和运营成本。
The second line contains \(N\) integers \(h_i\) \((0≤h_i≤10^9)\)— initial heights of pillars.
第二行包含整数 \(N\) - 柱子的初始高度。
Output
Print one integer — the minimal cost of restoration.
打印一个整数 - 恢复的最小成本。

感性理解，设最后每列的砖块数为 \(x\) ，当 \(x\) 很小或很大时，显然代价都比较大；当 \(x\) 处于最优解时，无论减少还是增多都会增大代价。所以合理猜测这是单峰函数。（至于严谨证明，我也不会；如果不信服这个感性理解，还是可以打个表出来看看）

于是我们三分 \(x\) 然后贪心即可。贪心的思路比较显然，具体看代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
ll A[MAXN];
ll n, a, r, m;
ll run(ll x) {
    ll low = 0, high = 0;
    for (int i = 0; i < n; ++i)
        if (A[i] < x)
            low += x - A[i];
        else
            high += A[i] - x;
    if (m > a + r)
        return low * a + high * r;
    else if (high > low)
        return m * low + (high - low) * r;
    else
        return m * high + (low - high) * a;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> a >> r >> m;
    for (int i = 0; i < n; ++i)
        cin >> A[i];
    int l = 0, r = 1e9, mid;
    ll ans = 1e18;
    while (l + 1 < r) // 直到只剩不到三个数为止
    {
        mid = (l + r) / 2;
        ll a1 = run(mid - 1), a2 = run(mid + 1);
        if (a1 > a2)
            ans = min(ans, a1), l = mid;
        else
            ans = min(ans, a2), r = mid;
    }
    ans = min(ans, run(l));
    ans = min(ans, run(r));
    cout << ans << endl;
    return 0;
}

这里因为是对整数进行操作，所以要更加注意边界问题。

算法笔记（目录）