Luogu P2085 最小函数值

题目传送门
一个优先队列的水题。
题目大意就是给出几个二次函数，并按照从小到大的顺序输出它们所能的函数值（$x$ 是正整数）

毕竟 $a, b, c$ 都是正整数，所以当 $x$ 是正整数时，$x=1$，$f(1)$ 取得最小值。

我们可以把函数值存入一个优先队列中，当然先取出的应该是最小值。（善用 STL）
像这样定义一个优先队列 priority_queue<func, vector<func>, greater<func> > que;
然后每次取出最小值输出并弹出，然后再压入 $f(x+1)$，如此往复。
定义一个结构体存函数，分别存函数的编号、自变量、函数值。

struct func {
    int id, x, val;
};

记得重载运算符，不然优先队列会出锅。

bool operator <(func a, func b) {
    return a.val < b.val;
}
bool operator >(func a, func b) {
    return a.val > b.val;
}

完整版

#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e4 + 5;
struct func {
    int id, x, val;
};
bool operator <(func a, func b) {
    return a.val < b.val;
}
bool operator >(func a, func b) {
    return a.val > b.val;
}
priority_queue<func, vector<func>, greater<func> > que;
int a[maxN], b[maxN], c[maxN];
int n, m;
int f(int i, int x) {
    return a[i] * x * x + b[i] * x + c[i];
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
        func tmp = (func){i, 1, f(i, 1)};
        que.push(tmp);
    }
    for (int i = 1; i <= m; i++) {
        func t = que.top();
        cout << t.val << ' ';
        que.pop();
        func tmp = (func){t.id, t.x + 1, f(t.id, t.x + 1)};
        que.push(tmp);
    }
    return 0;
}

然而这道题数据过水，完全可以暴力 $O(mn)$ 跑出来强行循环 m 次，每次比较 n 个函数值，找出最小的并输出。