洛谷-P2085 最小函数值(优先级队列)¶
题目描述¶
有 n*n* 个函数,分别为 F_1,F_2,\dots,F_n*F*1,F*2,…,*F**n。定义 F_i(x)=A_ix^2+B_ix+C+i(x\in\mathbb N*)F**i(x)=A**i**x*2+*B**i**x+C+i(x∈N∗)。给定这些 A_i*A**i*、B_i*B**i* 和 C_i*C**i*,请求出所有函数的所有函数值中最小的 m*m* 个(如有重复的要输出多个)。
输入格式¶
第一行输入两个正整数 n*n* 和 m*m*。
以下 n*n* 行每行三个正整数,其中第 i*i* 行的三个数分别为 A_i*A**i*、B_i*B**i* 和 C_i*C**i*。
输出格式¶
输出将这 n*n* 个函数所有可以生成的函数值排序后的前 m*m* 个元素。这 m*m* 个数应该输出到一行,用空格隔开。
输入输出样例¶
输入 #1
3 10
4 5 3
3 4 5
1 7 1
输出 #1
9 12 12 19 25 29 31 44 45 54
#include <bits/stdc++.h>
using namespace std;
struct coefficient
{
int a, b, c;
};
int n, m;
vector<coefficient> seq(10005);
struct Node
{
int number, value;
int k; //上一次计算的整数
Node(int a, int b, int c): number(a), value(b), k(c) {}
bool operator>(const Node & obj) const
{
return value > obj.value;
}
};
inline int calculate(const coefficient & obj, int x)
{ return obj.a * x *x + obj.b * x + obj.c; }
void solve()
{
priority_queue<Node, vector<Node>, greater<Node> > pq;
for (int i = 0; i < n; ++i) {
pq.push(Node(i, calculate(seq[i], 1), 1));
}
for (int i = 1; i <= m; ++i) {
Node tmp = pq.top(); pq.pop();
cout << tmp.value << ' ';
pq.push(Node(tmp.number, calculate(seq[tmp.number], tmp.k + 1), tmp.k + 1));
}
cout << endl;
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; ++i) cin >> seq[i].a >> seq[i].b >> seq[i].c;
solve();
return 0;
}
这道题很类似一本通-1333:【例2-2】Blah数集和洛谷-P1323 删数。
对于最多10^4个函数,每次要取出其中最小的函数值,容易往两个地方去思考,发现需要选取最大值的范围是确定的,也就是长度为n
,联想到滑动窗口,第二种思路是使用优先级队列,也就是最开始提到的两道题目。
使用优先级队列的时间复杂度是O(m \log n),可以接受,那么就需要使用一个结构体Node
,分别存储使用的函数对应的序号number
,函数在x = k
时的函数值value
,以及是通过整数k
计算得到的。维护一个小根堆,需要在结构体里面对比较运算符进行重载,具体点就是因为要使用小根堆,所以需要对>
运算符重载。这样每次取出堆顶端元素,然后把对应的k
加一,放回到堆里面。