LCP 59-搭桥过河

欢迎各位勇者来到力扣城，本次试炼主题为「搭桥过河」。勇者面前有一段长度为 num
的河流，河流可以划分为若干河道。每条河道上恰有一块浮木，wood[i] 记录了第 i 条河道上的浮木初始的覆盖范围。 -
当且仅当浮木与相邻河道的浮木覆盖范围有重叠时，勇者才可以在两条浮木间移动 - 勇者 仅能在岸上
通过花费一点「自然之力」，使任意一条浮木沿着河流移动一个单位距离请问勇者跨越这条河流，最少需要花费多少「自然之力」。 示例 1： > 输入：
num = 10, wood = [[1,2],[4,7],[8,9]] > 输出： 3 > 解释：如下图所示， > 将 [1,2] 浮木移动至
[3,4]，花费 2「自然之力」， > 将 [8,9] 浮木移动至 [7,8]，花费 1「自然之力」， > 此时勇者可以顺着
[3,4]->[4,7]->[7,8] 跨越河流， > 因此，勇者最少需要花费 3 点「自然之力」跨越这条河流 ![wood
(2).gif](https://pic.leetcode-cn.com/1648196478-ophADL-
wood%20\(2\).gif){:width=650px} 示例 2： > 输入： num = 10, wood = [[1,5],[1,1],[10,10],[6,7],[7,8]] > 输出： 10 > 解释： > 将 [1,5] 浮木移动至 [2,6]，花费
1「自然之力」， > 将 [1,1] 浮木移动至 [6,6]，花费 5「自然之力」， > 将 [10,10] 浮木移动至 [6,6]，花费 4「自然之力」，

此时勇者可以顺着 [2,6]->[6,6]->[6,6]->[6,7]->[7,8] 跨越河流， > 因此，勇者最少需要花费 10
点「自然之力」跨越这条河流 示例 3： > 输入： num = 5, wood = [[1,2],[2,4]] > 输出： 0 >
解释：勇者不需要移动浮木，仍可以跨越这条河流 提示: - 1 <= num <= 10^9 - 1 <= wood.length <= 10^5 - wood[i].length == 2 - 1 <= wood[i][0] <= wood[i][1] <= num

解法：数学

原题：https://atcoder.jp/contests/arc070/tasks/arc070_c 。抄原题就抄原题吧，抄个这么数学的…

网上已经有一个写得非常详细的题解，这里不再赘述推导过程，而是写几个题解中略过但是一些朋友可能看不太明白的点。

Q：f_i(x) 为什么是凸函数？

A：由归纳法证明。首先 f_1(x) = |x - l_1| 是凸函数，然后若 f_{i-1}(x) 是凸函数，由于 \min{f_{i-1,k} 这一项中 k 的取值范围是定长的，所以 \min{f_{i-1,k} 关于 x 也是凸函数。最后再加上一个凸函数绝对值，凸函数加凸函数仍然是凸函数。

Q：f_i(x) 的式子是怎么推导的？

A：主要是把 min 展开为大括号的那一段。

根据第一个 f_{i, j 的方程，我们知道 min 中 k 的取值范围是 [x - len_{i-1}, x + len_i]。f_i(x) 的式子假设 f_{i-1}(y) 是凸函数，且在 y \in [L, R] 是定值（也可以归纳法证明）。那么根据凸函数的性质：

当 k 的最大值比 L 还小时，即 x + len_i < L，即 x < L - len_i，应该让 k 取最大值（即取 f_{i-1}(k = x + len_i)）才能得到函数值的最小值。这就是大括号的第一个式子。
当 k 的最小值比 R 还大时，即 x - len_{i-1} > R，即 x > R - len_{i-1，应该让 k 取最小值（即取 f_{i-1}(k = x - len_{i-1})）才能得到函数值的最小值。这就是大括号的第三个式子。
其他情况，则 k 的取值范围包含 L 或者 R，取 f_{i-1}(k = L) = f_{i-1}(k = R) 即可。这就是大括号的第二个式子。

参考代码（c++）

class Solution {
    priority_queue<long long> L;
    priority_queue<long long, vector<long long>, greater<long long>> R;

public:
    long long buildBridge(int num, vector<vector<int>>& wood) {
        L.push(wood[0][0]); R.push(wood[0][0]);
        long long biasL = 0, biasR = 0, ans = 0;
        for (int i = 1; i < wood.size(); i++) {
            biasL -= wood[i][1] - wood[i][0];
            biasR += wood[i - 1][1] - wood[i - 1][0];
            long long l0 = L.top() + biasL;
            long long r0 = R.top() + biasR;
            int x = wood[i][0];
            if (x < l0) {
                ans += l0 - x;
                L.pop();
                L.push(x - biasL);
                L.push(x - biasL);
                R.push(l0 - biasR);
            } else if (x > r0) {
                ans += x - r0;
                R.pop();
                R.push(x - biasR);
                R.push(x - biasR);
                L.push(r0 - biasL);
            } else {
                L.push(x - biasL);
                R.push(x - biasR);
            }
        }
        return ans;
    }
};