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

函数 f(x) = | kx + a | + b，当x = -a/k 时最小，函数图像是一个V字形，有最小值。看到这个形状，我们很容易想到用三分法寻找最小值的位置。然而题目中的F(x) 是多个f(x) 的和，如果要用三分法，就必须保证F(x)在最小值左边单调递减（或平），在右边单调递增（或平），否则可能找到别的谷点（函数图形可以参考W的形状）。

这个证明我暂时没想到，但看到题目的标题是整数域三分，那么不管三七二十一先用再说。

三分法的具体做法是，计算区间[l, r]之间的两个三等分点mid1, mid2。比较 F(mid1) 和 F(mid2) 的大小，然后缩小范围（每次缩小三分之一），让其中较小那个点成为新区域的中点。

若 F(mid1) <= F(mid2)，区间[l, mid1, mid2, r]变成[l, mid1, mid2-1]。

若F(mid1) > F(mid2)，区间[l, mid1, mid2, r]变成[mid1+1, mid2-1]。

这样就保证了较小的那个点始终在新区域内，符合我们的直觉判断。

#include <iostream>
#include <vector>
using namespace std;

struct fun {
    int k, a, b;
};

long long getSum(vector<fun>& f, long long x) {
    long long ans = 0;
    for (fun& fi : f) {
        ans += abs(fi.k * x + fi.a) + fi.b;
    }
    return ans;
}

int main() {
    int t, n, l, r;
    cin >> t;
    while (t--) {
        cin >> n >> l >> r;
        vector<fun> f(n);
        for (int i = 0; i < n; ++i) {
            cin >> f[i].k >> f[i].a >> f[i].b;
        }
        while (l + 2 <= r) {
            int diff = (r - l) / 3;
            int mid1 = l + diff;
            int mid2 = r - diff;
            long long sum1 = getSum(f, mid1);
            long long sum2 = getSum(f, mid2);
            if (sum1 <= sum2) {
                r = mid2 - 1;
            } else {
                l = mid1 + 1;
            }
        }
        cout << min(getSum(f, l), getSum(f, r)) << endl;
    }
}
// 64 位输出请用 printf("%lld")