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。
分析
- 此题一看就用小根堆,通过枚举x,去将计算的函数值放入队列,但是放多少个呢,起初while循环条件是
q.size() <= m但是这样不对,因为可能前面的函数式用下一个x会比后面的函数用当前x计算出的值更小,于是用了个nm但是RE+TLE,后来试了个100m过了,但是可能是凑巧过了,此题一共有n*m个函数值,所以也可以采用大根堆来实现; - 用大根堆时候,只要队列元素不够m个,就直接加进去,否则就进行判断是否加入队列(维护一个只有m个元素的队列,解法一维护的是100*m个元素的队列);
小根堆
采用的是,枚举一个x,求出所有的函数值
#include <bits/stdc++.h>
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;
}
大根堆
遍历每个函数,对每个函数枚举m个x值;
#include <bits/stdc++.h>
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;
}