1370：最小函数值(minval)——优先队列

【题目描述】
有n个函数，分别为F1,F2,…,Fn。定义Fi(x)=Aix2+Bix+Ci(x∈N∗)。给定这些Ai、Bi和Ci，请求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。

【输入】
第一行输入两个正整数n和m。

以下n行每行三个正整数，其中第i行的三个数分别位Ai、Bi和Ci。输入数据保证Ai<=10，Bi<=100，Ci<=10000。

【输出】
将这n个函数所有可以生成的函数值排序后的前m个元素。这m个数应该输出到一行，用空格隔开。

【输入样例】
3 10
4 5 3
3 4 5
1 7 1
【输出样例】
9 12 12 19 25 29 31 44 45 54
【提示】
【数据规模】

n,m≤10000。

分析

1. 此题一看就用小根堆，通过枚举x，去将计算的函数值放入队列，但是放多少个呢，起初while循环条件是q.size() <= m 但是这样不对，因为可能前面的函数式用下一个x会比后面的函数用当前x计算出的值更小，于是用了个nm但是RE+TLE，后来试了个100m过了，但是可能是凑巧过了，此题一共有n*m个函数值，所以也可以采用大根堆来实现；
2. 用大根堆时候，只要队列元素不够m个，就直接加进去，否则就进行判断是否加入队列（维护一个只有m个元素的队列，解法一维护的是100*m个元素的队列）；

小根堆

采用的是，枚举一个x，求出所有的函数值

#include 

using namespace std;

const int N = 10010;
//小根堆
priority_queue<int, vector<int>, greater<int>> q;
int n, m;
int a[N], b[N], c[N];

int main() {
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i] >> c[i];
    }
    int x = 1;//枚举x
    while (q.size() <= 100 * m) {
        for (int i = 0; i < n; ++i) {
            q.push(a[i] * x * x + b[i] * x + c[i]);
        }
        x++;
    }
    while (m--) {
        cout << q.top() << " ";
        q.pop();
    }
    return 0;
}



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

大根堆

遍历每个函数，对每个函数枚举m个x值；

#include 

using namespace std;

const int N = 10010;
//大根堆
priority_queue<int> q;
int n, m;
int a[N], b[N], c[N], ans[N];

int main() {
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i] >> c[i];
    }
    //n个函数，每个函数枚举m个x的取值
    for (int i = 0; i < n; ++i) {
        //枚举x
        for (int x = 1; x <= m; ++x) {
            int f = a[i] * x * x + b[i] * x + c[i];
            if (q.size() < m)
                q.push(f);
            else {
                if (f < q.top()) {
                    q.pop();
                    q.push(f);
                }
            }
        }
    }

    for (int i = 0; i < m; ++i) {
        ans[i] = q.top();
        q.pop();
    }
    for (int i = m - 1; i >= 0; --i) {
        cout << ans[i] << " ";
    }
    return 0;
}



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