T28912: 绝对值函数最值

math, http://cs101.openjudge.cn/practice/28912/

小明在研究一个含有绝对值的函数

f(x)=c1∣a1x+b1∣+c2∣a2x+b2∣+⋯+cn∣anx+bn∣

其中 ci∣aix+bi∣ 表示 ai × x+bi 的绝对值乘以 ci。

小明打算计算出 x=0,1,⋯ ,M 时 f(x) 的值，然后找出这 M+1个值中的最大值和最小值。

但是计算所有 f(x)的值的工作量太大，所以他打算把任务交给你，你只需要找出这些值中的最大值和最小值即可。

输入

第1行，2个正整数 n,M。1 ≤ n ≤ 3000；1 ≤ M ≤ 10^9；

接下来 n行，每行三个整数 ai,bi,ci。−1000 ≤ ai ≤ 1000；−10^9 ≤ bi ≤ 10^9；−1000 ≤ ci ≤ 1000。

输出

输出两个整数，表示当 x=0,1,⋯ ,M时，M+1个 f(x)的值中的最大值和最小值。用空格分隔。

样例输入

sample1 input:
3 5
1 3 1
1 -4 -4
-2 5 1

sample1 output:
10 -8

样例输出

sample2 input:
4 10
-1 -4 0
0 5 4
1 0 -5
2 -4 -3

sample2 output:
10 -78

提示

math，用数学手段优化枚举

来源

2024-TA-lhw

思路：分段线性函数的极值一定在分段点（ $x = - b / a$ ）或区间端点处取得。由于 $x$ 取整数，检查分段点附近的整数即可。

python

import math

n, M = map(int, input().split())
params = [list(map(int, input().split())) for _ in range(n)]

points = {0, M}
for a, b, c in params:
    if a != 0:
        x_f = -b / a
        for dx in [math.floor(x_f), math.ceil(x_f)]:
            if 0 <= dx <= M:
                points.add(dx)

results = []
for x in points:
    val = sum(c * abs(a * x + b) for a, b, c in params)
    results.append(val)

print(f"{max(results)} {min(results)}")

这道题目要求计算含有绝对值的函数 $f (x) = \sum_{i = 1}^{n} c_{i} | a_{i} x + b_{i} |$ 在离散整数点 $x \in {0, 1, \dots, M}$ 上的最大值和最小值。由于 $M$ 高达 $10^{9}$ ，直接枚举所有 $x$ 的值是不可能的。
算法分析
分段线性性质：函数 $f (x)$ 是多个分段线性函数（绝对值函数）的叠加。因此， $f (x)$ 本身也是一个分段线性且连续的函数。
最值位置：在连续区间 $[0, M]$ 内，一个分段线性函数的最值只能出现在两个地方：
区间的端点（即 $x = 0$ 和 $x = M$ ）。
函数的“拐点”（即绝对值内部等于 0 的点： $a_{i} x + b_{i} = 0 \Rightarrow x = - b_{i} / a_{i}$ ）。
离散最值：由于题目要求 $x$ 必须是整数，对于每一个落在 $(0, M)$ 之间的拐点 $v_{i} = - b_{i} / a_{i}$ ，我们需要检查其相邻的两个整数点 $⌊ v_{i} ⌋$ 和 $⌈ v_{i} ⌉$ 。
优化计算：如果对于每一个候选点（共约 $2 n + 2$ 个）都重新计算 $f (x)$ ，总复杂度为 $O (n^{2})$ 。

T28912: 绝对值函数最值 ​

T28912: 绝对值函数最值