A24 三分整数 • EH's Blog

题目情境#

暂无题目链接，本题为后续自行补充的，使用极其广泛，正确性已验证

题目描述

定义含绝对值的一元一次函数 $f(x)=|kx+a|+b$ ( $x\in \mathbb{Z}$ )，其中 $k$ 为由外部给定的正整数， $a,b$ 为整数。

现在，对于给定的 $n$ 个含绝对值的一元一次函数，定义

$F(x)=f_1(x)+f_2(x)+\cdots+f_n(x)，$

求解 $F(x)$ 在区间 $[l,r]$ 上的最小值。

输入格式

每个测试文件包含多组测试数据。第一行输入一个整数 $T$ ( $1\le T\le 5\times 10^5$ ) 代表数据组数。每组测试数据描述如下：

第一行输入三个整数 $n,l,r$ ，其中 $1\le n\le 5\times 10^5$ ， $-10^7\le l\le r\le 10^7$ ，表示函数个数和值域；
接下来 $n$ 行，每行输入三个整数 $k_i,a_i,b_i$ ，用于描述第 $i$ 个函数 $f_i(x)=|k_ix+a_i|+b_i$ ，满足 $0\le k_i,|a_i|,|b_i|\le 10^6$ 。

此外，保证所有测试数据中 $n$ 的总和不超过 $5\times 10^5$ 。

输出格式

对于每组测试数据，在一行输出一个整数，表示 $F(x)$ 在区间 $[l,r]$ 上的最小值。

输入输出样例

输入 #1

3
4 -15 20
1 -11 2
2 -2 0
1 20 -20
0 0 -10
3 10 100000
1 -11 -4
2 5 -10
1 -13 -10
3 12 100000
1 -11 -4
2 5 -10
1 -13 -10

plaintext

输出 #1

3
5
7

plaintext

算法解析#

每个函数 $f_i(x)=|k_ix+a_i|+b_i$ 是一个凸的分段线性函数，若将它们相加得到的 $F(x)$ 依然是一个凸的分段线性函数。因为 $x$ 要求取整数，所以可以在整数区间上使用离散的三分法求最小值。

具体做法：

计算当前区间 $[l,r]$ 的两个三分点 $m_1=l+(r-l)//3$ 和 $m_2=r-(r-l)//3$ ；
分别计算 $F(m_1)$ 和 $F(m_2)$ ；
若 $F(m_1)\le F(m_2)$ ，则最小值可能在左半区间，令 $r=m_2-1$ ；否则令 $l=m_1+1$ ；
重复上述过程，直到区间缩小到常数范围，再直接枚举区间端点取最小值。

由于每个测试数据组的函数个数之和总计不超过 $5\times 10^5$ ，这个方法的总时间复杂度可以保证在可接受范围内。

Python代码实现#

def get_sum(f, x):
    total = 0
    for k, a, b in f:
        total += abs(k * x + a) + b
    return total

 t = int(input())
for _ in range(t):
    n, l, r = map(int, input().split())
    f = [tuple(map(int, input().split())) for _ in range(n)]

    while l + 2 <= r:
        diff = (r - l) // 3
        mid1 = l + diff
        mid2 = r - diff
        sum1 = get_sum(f, mid1)
        sum2 = get_sum(f, mid2)
        if sum1 <= sum2:
            r = mid2 - 1
        else:
            l = mid1 + 1

    print(min(get_sum(f, l), get_sum(f, r)))

python

C++代码实现#

#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")