【题目来源】
洛谷：P2085 最小函数值 - 洛谷
【题目描述】
有 \(n\) 个函数，分别为 \(F_1,F_2,\dots,F_n\)。定义 \(F_i(x)=A_ix^2+B_ix+C_i(x\in\mathbb N*)\)。给定这些 \(A_i\)、\(B_i\) 和 \(C_i\)，请求出所有函数的所有函数值中最小的 \(m\) 个（如有重复的要输出多个）。
【输入】
第一行输入两个正整数 \(n\) 和 \(m\)。
以下 \(n\) 行每行三个正整数，其中第 \(i\) 行的三个数分别为 \(A_i\)、\(B_i\) 和 \(C_i\)。
【输出】
输出将这 \(n\) 个函数所有可以生成的函数值排序后的前 \(m\) 个元素。这 \(m\) 个数应该输出到一行，用空格隔开。
【输入样例】
3 10
4 5 3
3 4 5
1 7 1
【输出样例】
9 12 12 19 25 29 31 44 45 54
【算法标签】
《洛谷 P2085 最小函数值》 #数学# #堆# #排序# #优先队列#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 10005;// 定义结构体表示节点
struct Node
{int idx; // 函数编号，表示这是第几个二次函数int x; // 当前x的值int v; // 函数值，即A*x² + B*x + C// 重载>运算符，用于优先队列（小根堆）// 注意：优先队列默认是大根堆，这里用greater<Node>变成小根堆// 所以这里重载>运算符实际上是比较函数值大小bool operator>(const Node &t) const {return v > t.v; // 值大的节点优先级低}
};int n, m, A[N], B[N], C[N];// 优先队列，存储节点，小根堆
priority_queue<Node, vector<Node>, greater<Node> > pq;// 广度优先搜索（实际上是多路归并）
void bfs()
{// 初始化优先队列// 对于每个二次函数，计算x=1时的值for (int i=1; i<=n; i++){// 创建节点：函数编号i，x=1，计算函数值Node t = {i, 1, A[i] + B[i] + C[i]}; // 当x=1时，A[1]*1² + B[1]*1 + C[1]pq.push(t); // 入队}// 输出前m小的函数值while (m--){// 取出当前最小的函数值节点Node t = pq.top();cout << t.v << " "; // 输出当前最小函数值pq.pop(); // 弹出// 将x加1，计算新的函数值t.x++;t.v = A[t.idx] * t.x * t.x + B[t.idx] * t.x + C[t.idx];// 将新节点加入优先队列pq.push(t);}
}signed main() // 因为#define int long long，所以用signed main
{cin >> n >> m; // 读入n个函数，需要前m小的值// 读入每个二次函数的系数A、B、Cfor (int i=1; i<=n; i++){cin >> A[i] >> B[i] >> C[i];}// 执行多路归并算法bfs();return 0;
}
【运行结果】
3 10
4 5 3
3 4 5
1 7 1
9 12 12 19 25 29 31 44 45 54