洛谷 P2085 最小函数值

// 第一反应：把所有函数值都算出来，排个序，取前 m 个
//
// 「所有」有多少个？—— 每个函数只有前 m 个值有可能进前 m 名（第 m+1 个已经比 m 个数都大了），
// 所以是 **n × m = 10⁴ × 10⁴ = 10⁸ 个值**。
//
// ⚠⚠ 这一版**先撞的是内存，不是时间**：
//   10⁸ 个 int = **400 MB**，而题面只给 **128 MB** ⇒ MLE。
//   （就算内存管够，排 10⁸ 个数也要十几秒。）
// ⇒ 「答案对但跑不完」的又一次，而这次的墙是内存
//   （[第 24 章 P1853](/sol/p1853/)、[第 28 章 P2704](/sol/p2704/) 都撞过同一堵墙）。

#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<long long> all;
    all.reserve((size_t)n * m);                    // ⚠ 顶格就是 10^8 个
    for (int i = 0; i < n; i++) {
        long long a, b, c;
        cin >> a >> b >> c;
        for (int x = 1; x <= m; x++) all.push_back(a * x * x + b * x + c);
    }
    sort(all.begin(), all.end());

    string out;
    for (int k = 0; k < m; k++) { if (k) out += ' '; out += to_string(all[k]); }
    out += '\n';
    cout << out;
    return 0;
}

// 顺着上一版往下改：**不用把它们全存下来** —— 手上只留「到目前为止最小的 m 个」
//
//   每读进一个函数，就算出它的前 m 个值（本来就是递增的），
//   和手上那 m 个**归并**一遍，只保留前 m 个。
//   ⇒ 空间从 400 MB 掉到 O(m)，时间是 O(nm) = 10⁸ 次简单操作。
//
// ★★ **而这一版就已经能 AC 了**（顶格本机 0.28 秒 / 时限 1 秒，第 ③ 步那张表）——
//   这本书反复强调的那件事：**不写到最优也能过，先把能过的那一版写出来。**
// ⚠ 它和堆那版差 6.6 倍，而两版都在时限里 ⇒ 选堆的理由不是「非它不可」，是它**说得清**。

#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<long long> best, cur, tmp;
    best.reserve(m); cur.reserve(m); tmp.reserve(m);
    for (int i = 0; i < n; i++) {
        long long a, b, c;
        cin >> a >> b >> c;
        cur.clear();
        for (int x = 1; x <= m; x++) cur.push_back(a * x * x + b * x + c);
        tmp.clear();
        size_t p = 0, q = 0;
        while (tmp.size() < (size_t)m && (p < best.size() || q < cur.size())) {
            if (q >= cur.size() || (p < best.size() && best[p] <= cur[q])) tmp.push_back(best[p++]);
            else tmp.push_back(cur[q++]);
        }
        best.swap(tmp);
    }

    string out;
    for (int k = 0; k < m; k++) { if (k) out += ' '; out += to_string(best[k]); }
    out += '\n';
    cout << out;
    return 0;
}

// P2085 最小函数值 —— ★ 这一版就能 AC：**多路归并**（堆里永远只放 n 个候选）
//
// ============ 先把题面读成一句话 ============
//   F(x) = A x² + B x + C，而题面保证 **A ≥ 1、B ≥ 0、x ≥ 1**
//   ⇒ 每个函数在 x = 1, 2, 3, … 上的取值是**严格递增**的。
//   ⇒ 于是这道题变成：**n 个已经排好序的序列，求它们并起来的前 m 小**。
//     （⚠ 那句 A ≥ 1 是**命门**，不是背景 —— 第 ⑤ 步会把它称一称。）
//
// ============ 关键一步：不用把 n × m 个值造出来 ============
//   每个序列**只有它的当前头部**有资格当下一个最小值（后面的都比它大）。
//   ⇒ 堆里永远只放 **n 个候选**（每个函数一个），取一次就把那个函数往后推一格。
//   ⇒ 时间 O((n + m) log n)，空间 O(n) —— 而暴力是 n × m = 10⁸ 个值、400 MB。
//
// ★ 这就是[本章第 12 步](/ch/37-heap/)那句话的又一个现场：
//   **堆的本事是「只看该看的那几个」** —— 它需要的条件最少，来一个看一个。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long v;     // 当前值 F_i(x)
    int i, x;        // 来自第 i 个函数，当前的 x
    bool operator>(const Node& o) const { return v > o.v; }
};

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<long long> A(n), B(n), C(n);
    priority_queue<Node, vector<Node>, greater<Node>> q;      // ★ 小根堆
    for (int i = 0; i < n; i++) {
        cin >> A[i] >> B[i] >> C[i];
        long long v = A[i] * 1 * 1 + B[i] * 1 + C[i];         // x = 1，题面 x ∈ N*
        q.push({v, i, 1});
    }

    string out;
    for (int k = 0; k < m; k++) {
        Node t = q.top();
        q.pop();
        if (k) out += ' ';
        out += to_string(t.v);
        int i = t.i, x = t.x + 1;                             // 那个函数往后推一格
        long long v = A[i] * x * x + B[i] * x + C[i];
        q.push({v, i, x});
    }
    out += '\n';
    cout << out;
    return 0;
}

// ✗ 错法一：x 从 0 开始
//
// 题面写的是 `F_i(x) = A_i x² + B_i x + C_i (x ∈ N*)` ——
// **`N*` 是正整数集，不含 0**（`N` 才含）。这一个星号最容易被略过。
//
// ⚠ 而它的后果非常大：x = 0 时 F(0) = C，而题面允许 `C ≥ 0`
//   ⇒ 凭空多出 n 个很小的值，前 m 名整个被它们挤掉。
// ★ 官方样例第一个数就变了（正解 9，它打 1），一测就死。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long v; int i, x;
    bool operator>(const Node& o) const { return v > o.v; }
};

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<long long> A(n), B(n), C(n);
    priority_queue<Node, vector<Node>, greater<Node>> q;
    for (int i = 0; i < n; i++) {
        cin >> A[i] >> B[i] >> C[i];
        q.push({C[i], i, 0});                     // ⚠ x 从 0 起
    }
    string out;
    for (int k = 0; k < m; k++) {
        Node t = q.top(); q.pop();
        if (k) out += ' ';
        out += to_string(t.v);
        int i = t.i, x = t.x + 1;
        q.push({A[i] * x * x + B[i] * x + C[i], i, x});
    }
    out += '\n';
    cout << out;
    return 0;
}