最小函数值(minval)

题目描述

给定 $n$ 个二次函数 $F_i(x)=A_ix^2+B_ix+C_i$ （ $x\in\mathbb{N}^*$ ，系数均为正整数， $A_i\le 10$ 、 $B_i\le 100$ 、 $C_i\le 10^4$ ），求所有函数值中最小的 $m$ 个（重复值按多次输出）， $1\le n,m\le 10^4$ 。输入第一行 $n,m$ ，随后 $n$ 行每行 $A_i,B_i,C_i$ ；输出一行 $m$ 个空格隔开的数。样例输入 3 10 与三行 4 5 3、3 4 5、1 7 1，输出 9 12 12 19 25 29 31 44 45 54。

思路

系数全为正，故 $F_i(x+1)-F_i(x)=A_i(2x+1)+B_i>0$ ，每个函数在 $x\ge 1$ 上严格递增，可把其自变量序列看成一条有序链。于是问题变成 $n$ 条有序链归并取前 $m$ 项：小根堆里放每条链的当前候选 $F_i(1)$ ，弹出 $m$ 次堆顶即为答案，每次弹出后把该函数的 $F_i(x+1)$ 压回堆。堆中最多 $n$ 个元素，时间复杂度 $O((n+m)\log n)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys
import heapq


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    # 每个函数读成，每个函数当前只推进一个"指针"x
    fs = [(a, b, c) for a, b, c in zip(data, data, data)]  # n 个二次函数

    # 堆里放（函数值, 所属函数编号，当前自变量 x）：f 在 x≥1 上严格单调递增，
    # 所以每个函数只需保留最小的一个候选值 F_i(1)，弹出后再压入 F_i(x+1)。
    heap = [(a + b + c, i, 1) for i, (a, b, c) in enumerate(fs)]  # 初始 x = 1
    heapq.heapify(heap)

    out: list[int] = []
    for _ in range(m):
        v, i, x = heapq.heappop(heap)
        out.append(v)
        a, b, c = fs[i]
        x += 1  # 该函数下一个自变量
        heapq.heappush(heap, (a * x * x + b * x + c, i, x))

    print(*out)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:13
 * update_at: 2026-10-05 12:13
 */

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

typedef long long ll;

const int MAXN = 10005; // n <= 10^4

ll A[MAXN]; // A[i]：第 i 个函数的二次项系数
ll B[MAXN]; // B[i]：第 i 个函数的一次项系数
ll C[MAXN]; // C[i]：第 i 个函数的常数项

// 堆元素：一个候选函数值，以及它来自哪个函数、对应哪个自变量。
// idx 是数组下标，n <= 10^4，用 int 即可。
struct Node {
    ll value;
    int idx;
    ll x;
};

// 小根堆的比较：函数值小的优先，值相同时函数编号小的优先（顺序不影响答案）。
struct Cmp {
    bool operator()(const Node &p, const Node &q) const {
        if (p.value != q.value) {
            return p.value > q.value;
        }
        return p.idx > q.idx;
    }
};

priority_queue<Node, vector<Node>, Cmp> heap; // 保存每个函数"指针"位置上的候选值

// 计算第 i 个函数在 x 处的取值 F_i(x) = A_i*x^2 + B_i*x + C_i。
ll calc(int i, ll x) {
    return A[i] * x * x + B[i] * x + C[i];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m;
    cin >> n >> m;

    // 系数全为正，F_i(x+1) - F_i(x) = A_i*(2x+1) + B_i > 0，
    // 所以每个函数在 x >= 1 上严格递增，可看成 n 条有序链做多路归并。
    for (int i = 1; i <= n; i++) {
        cin >> A[i] >> B[i] >> C[i];
        Node first;
        first.value = calc(i, 1);
        first.idx = i;
        first.x = 1;
        heap.push(first);
    }

    // 弹出 m 次堆顶即为前 m 小的函数值；每弹出一个，就把该函数的下一个候选压回堆。
    for (ll k = 1; k <= m; k++) {
        Node top = heap.top();
        heap.pop();

        if (k > 1) {
            cout << ' ';
        }
        cout << top.value;

        ll nxt = top.x + 1;
        Node next_node;
        next_node.value = calc(top.idx, nxt);
        next_node.idx = top.idx;
        next_node.x = nxt;
        heap.push(next_node);
    }
    cout << '\n';

    return 0;
}