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 来解决，因为 M 最大可以达到 10^9，直接计算会超时。需要用数学方法来分析函数 f (x) 的性质，找到它在区间 [0, M] 上的最大值和最小值。

核心思路

函数 f (x) 是一个由多个绝对值项线性组合而成的函数。每个绝对值项 |a_i x + b_i| 的图像是一个 “V” 字形，当 a_i x + b_i = 0 时，也就是在 x = -b_i / a_i (当 a_i != 0 时)，函数取得最小值 0。

整个函数 f (x) 的图像是这些 “V” 字形的叠加。它的特点是：

分段线性：在两个相邻的 “临界点” 之间，函数 f (x) 是线性的，即它的斜率是固定的。
临界点：这些临界点就是各个绝对值项的 “V” 字形的顶点对应的 x 值，即 x = -b_i / a_i (当 a_i != 0 时)。

因此，函数 f (x) 的最大值和最小值只能出现在以下位置：

区间的两个端点：x = 0 和 x = M。
落在区间 [0, M] 内的所有临界点。

算法步骤

生成所有临界点：遍历每一个绝对值项，计算出它的临界点 x_candidate = -b_i / a_i (仅当 a_i != 0 时)。
筛选有效临界点：由于我们只关心区间 [0, M] 内的函数值，因此需要筛选出那些满足 0 ≤ x_candidate ≤ M 的临界点。
扩展候选点集：将区间的两个端点 0 和 M 也加入到候选点集中。
计算函数值：对于候选点集中的每一个 x 值，计算 f (x) 的值。
寻找最值：在所有计算出的 f (x) 值中，找出最大值和最小值。

注意事项

整数 x：题目要求 x 必须是整数（0, 1, ..., M）。而计算出的临界点 x_candidate 很可能是一个小数。直接计算这个小数 x 对应的 f (x) 值是没有意义的。我们需要找到这个临界点 两侧最近的整数，即 floor(x_candidate) 和 ceil(x_candidate)，并检查这两个整数是否在 [0, M] 区间内。如果在，就把它们加入到候选点集中。
a_i = 0 的情况：当 a_i = 0 时，绝对值项变为 |0 * x + b_i| = |b_i|，这是一个常数，不影响函数 f (x) 的单调性，也不会产生新的临界点。
重复的候选点：不同的绝对值项可能会产生相同的临界点，或者我们计算出的 floor(x_candidate) 和 ceil(x_candidate) 可能与区间端点重合。我们需要使用一个集合（Set）来存储候选点，以避免重复计算。

Python 代码实现

python

import math

def main():
    n, M = map(int, input().split())
    terms = []
    for _ in range(n):
        a, b, c = map(int, input().split())
        terms.append((a, b, c))

    # 1. 生成并筛选候选点
    candidates = set()
    candidates.add(0)
    candidates.add(M)

    for a, b, c in terms:
        if a == 0:
            continue
        
        # 计算临界点 x = -b/a
        # 使用浮点数计算可能会有精度问题，但对于找 floor 和 ceil 影响不大
        # 更稳妥的方法是用分数比较，这里为了代码简洁，使用浮点数
        x_candidate = -b / a
        
        # 检查 x_candidate 是否在 [0, M] 区间内（允许微小的浮点误差）
        if -1e-9 <= x_candidate <= M + 1e-9:
            # 找到临界点两侧最近的整数
            left_x = math.floor(x_candidate)
            right_x = math.ceil(x_candidate)
            
            # 检查这些整数是否在 [0, M] 区间内，如果是则加入候选集
            if 0 <= left_x <= M:
                candidates.add(left_x)
            if 0 <= right_x <= M:
                candidates.add(right_x)

    # 2. 计算所有候选点的函数值 f(x)
    min_value = float('inf')
    max_value = -float('inf')
    
    for x in candidates:
        current_sum = 0
        for a, b, c in terms:
            current_sum += c * abs(a * x + b)
        
        if current_sum < min_value:
            min_value = current_sum
        if current_sum > max_value:
            max_value = current_sum
            
    print(max_value, min_value)

if __name__ == "__main__":
    main()

代码解析

main 函数：程序的主入口。
读取输入：读取 n 和 M，然后读取 n 个三元组 (a_i, b_i, c_i) 并存储在 terms 列表中。
candidates = set()：使用集合 candidates 来存储所有需要计算函数值的 x 坐标，以自动处理重复值。
candidates.add(0) 和 candidates.add(M)：首先将区间的两个端点加入候选集。
遍历 terms：
- 如果 a == 0，跳过，因为它不产生临界点。
- 计算 x_candidate = -b / a。
- if -1e-9 <= x_candidate <= M + 1e-9:：这是一个健壮性判断，用于处理因浮点数精度问题导致的微小偏差。例如，一个本应是 0 的值可能计算为 -1e-15。
- math.floor(x_candidate) 和 math.ceil(x_candidate)：找到临界点左右的整数。例如，如果 x_candidate 是 3.7，我们就检查 3 和 4。如果 x_candidate 是 5.0，那么 floor 和 ceil 都是 5，add 操作会自动去重。
- 将有效的整数 x 加入 candidates 集合。
计算和比较：
- 初始化 min_value 为正无穷大，max_value 为负无穷大。
- 遍历 candidates 集合中的每一个 x。
- 对于每个 x，计算 f(x) 的值。
- 更新 min_value 和 max_value。
输出结果：打印最终找到的最大值和最小值。

这个算法的时间复杂度主要取决于候选点的数量。每个绝对值项最多贡献 2 个候选点（floor 和 ceil），所以候选点的总数是 O (n) 级别的。对于每个候选点，计算 f (x) 需要 O (n) 的时间。因此，总的时间复杂度是 O (n^2)，对于 n ≤ 3000 的限制来说，这是完全可以接受的。

T28912: 绝对值函数最值 ​

T28912: 绝对值函数最值