题解 | 【模板】整数域三分

import java.util.*;
import java.io.*;

public class Main {
    static class Function {
        int k, a;
        Function(int k, int a) {
            this.k = k;
            this.a = a;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            String[] line = br.readLine().split(" ");
            int n = Integer.parseInt(line[0]);
            int l = Integer.parseInt(line[1]);
            int r = Integer.parseInt(line[2]);
            long S = 0;
            List<Function> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                line = br.readLine().split(" ");
                int k = Integer.parseInt(line[0]);
                int a = Integer.parseInt(line[1]);
                int b = Integer.parseInt(line[2]);
                S += b;
                if (k == 0) {
                    S += Math.abs(a);
                } else {
                    list.add(new Function(k, a));
                }
            }
            int m = list.size();
            if (m == 0) {
                bw.write(S + "\n");
                continue;
            }
            Collections.sort(list, (f1, f2) -> {
                long left = (long) (-f1.a) * f2.k;
                long right = (long) (-f2.a) * f1.k;
                return Long.compare(left, right);
            });
            long totalK = 0;
            long totalKC = 0;
            for (Function func : list) {
                totalK += func.k;
                totalKC -= func.a;
            }
            long[] prefixW = new long[m];
            long[] prefixC = new long[m];
            prefixW[0] = list.get(0).k;
            prefixC[0] = -list.get(0).a;
            for (int i = 1; i < m; i++) {
                prefixW[i] = prefixW[i - 1] + list.get(i).k;
                prefixC[i] = prefixC[i - 1] - list.get(i).a;
            }
            int low = l, high = r;
            long ans = Long.MAX_VALUE;
            while (high - low > 2) {
                int mid1 = low + (high - low) / 3;
                int mid2 = high - (high - low) / 3;
                long f1 = F(mid1, list, prefixW, prefixC, totalK, totalKC, S);
                long f2 = F(mid2, list, prefixW, prefixC, totalK, totalKC, S);
                if (f1 < f2) {
                    high = mid2 - 1;
                } else if (f1 > f2) {
                    low = mid1 + 1;
                } else {
                    low = mid1 + 1;
                    high = mid2 - 1;
                }
            }
            for (int x = low; x <= high; x++) {
                long fx = F(x, list, prefixW, prefixC, totalK, totalKC, S);
                if (fx < ans) ans = fx;
            }
            bw.write(ans + "\n");
        }
        bw.flush();
    }

    private static long F(int x, List<Function> list, long[] prefixW, long[] prefixC, long totalK, long totalKC, long S) {
        int low = 0, high = list.size() - 1;
        int pos = -1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            Function func = list.get(mid);
            if ((long) func.a >= -(long) x * func.k) {
                pos = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        long sum_left_k = (pos == -1) ? 0 : prefixW[pos];
        long sum_left_kc = (pos == -1) ? 0 : prefixC[pos];
        long F1 = (long) x * (2 * sum_left_k - totalK) + (totalKC - 2 * sum_left_kc);
        return F1 + S;
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 常数处理：当 𝑘𝑖=0 时，函数为常数，直接加入总和 𝑆。
2. 排序：对 𝑘𝑖>0 的函数按 𝑐𝑖=−𝑎𝑖/𝑘𝑖 排序，使用交叉相乘避免浮点数精度问题。
3. 前缀和：计算权重和 𝑝𝑟𝑒𝑓𝑖𝑥𝑊 及常数和 𝑝𝑟𝑒𝑓𝑖𝑥𝐶 的前缀数组，用于快速计算 𝐹(𝑥)。
4. 三分搜索：利用凸函数性质，在区间 [𝑙,𝑟] 上三分查找最小值点。
5. 二分定位：对每个 𝑥，二分查找满足 𝑐𝑖≤𝑥 的最大位置，使用前缀和公式高效计算函数值。