斜率优化

• OI Wiki: https://oi-wiki.org/dp/opt/slope/

题目	难度
LCP 24. 数字游戏	困难	Slope Trick
LCP 59. 搭桥过河	困难	Slope Trick
$2263. 数组变为有序的最小操作次数	困难	TODO

参考链接

• https://codeforces.com/blog/entry/47821
• https://codeforces.com/blog/entry/77298
• https://leetcode.cn/problems/5TxKeK/solution/xie-lu-you-hua-by-fzldq-9wt4/
• https://leetcode.cn/problems/make-array-non-decreasing-or-non-increasing/

LCP 24. 数字游戏

import java.util.PriorityQueue;

public class SolutionLCP24 {
    private static final int MOD = (int) (1e9 + 7);

    public int[] numsGame(int[] nums) {
        int n = nums.length;
        long minf = 0;
        int[] res = new int[n];
        PriorityQueue<Integer> L = new PriorityQueue<>();
        PriorityQueue<Integer> R = new PriorityQueue<>();
        L.add(Integer.MAX_VALUE / 2);
        R.add(Integer.MAX_VALUE / 2);
        for (int i = 0; i < n; i++) {
            int a = nums[i];
            minf += Math.max(0, -L.element() + i - a);
            L.add(-a + i);
            R.add(-L.remove());
            minf += Math.max(0, a - R.element() - i);
            R.add(a - i);
            L.add(-R.remove());
            res[i] = (int) (minf % MOD);
        }
        return res;
    }
}

LCP 59. 搭桥过河

import java.util.Comparator;
import java.util.PriorityQueue;

public class SolutionLCP59 {
    // https://leetcode.cn/problems/NfY1m5/solution/by-tsreaper-qhvj/
    public long buildBridge(int num, int[][] wood) {
        PriorityQueue<Long> L = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Long> R = new PriorityQueue<>();
        L.add((long) wood[0][0]);
        R.add((long) wood[0][0]);
        long biasL = 0, biasR = 0, ans = 0;
        for (int i = 1; i < wood.length; i++) {
            biasL -= wood[i][1] - wood[i][0];
            biasR += wood[i - 1][1] - wood[i - 1][0];
            long l0 = L.element() + biasL;
            long r0 = R.element() + biasR;
            int x = wood[i][0];
            if (x < l0) {
                ans += l0 - x;
                L.poll();
                L.add(x - biasL);
                L.add(x - biasL);
                R.add(l0 - biasR);
            } else if (x > r0) {
                ans += x - r0;
                R.poll();
                R.add(x - biasR);
                R.add(x - biasR);
                L.add(r0 - biasL);
            } else {
                L.add(x - biasL);
                R.add(x - biasR);
            }
        }
        return ans;
    }
}

（全文完）