洛谷P2085——最小函數值

題目描述

有n個函數，分別為\(F_1,F_2,...,F_n\)。定義\(F_i(x)=A_i*x^2+B_i*x+C_i (x∈N*)\)。給定這些\(A_i、B_i和C_i\)，請求出所有函數的所有函數值中最小的m個（如有重覆的要輸出多個）。

輸入格式

輸入數據：第一行輸入兩個正整數n和m。以下n行每行三個正整數，其中第i行的三個數分別位Ai、Bi和Ci。\(Ai<=10，Bi<=100，Ci<=10 000\)。

輸出格式

輸出數據：輸出將這n個函數所有可以生成的函數值排序後的前m個元素。這m個數應該輸出到一行，用空格隔開。

思路

堆排序，註意要加greater<int>，詳見此篇文章

代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue <ll, vector<ll>, greater<ll> > heap;
int main() {
    register ll n,m;
    scanf("%lld%lld",&n,&m);
    for(register int i = 0;i<n;++i) {
        register ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        for(register int j = 1;j<=100;++j) {
            heap.push((int)a*j*j+b*j+c);
        }
    }
    while(m--) {
        printf("%lld ",heap.top());
        heap.pop();
    }
    return 0;
}