P2085 最小函数值
题目 【多路归并】
思路
多路合并的思想
每个函数为一路，每一路从1...开始单调递增
维护指针数组
维护小根堆，每次取最小的元素，并修改指针
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10010;
struct F{
int a,b,c;
LL get(LL x) {
return x*x*a+x*b+c;
}
}f[N];
struct Node {
LL v;
int id;
bool operator<(const Node& t) const {
return v > t.v;
}
};
int p[N];
priority_queue<Node> pq;
int main()
{
int n,m;
cin>>n>>m;
for(int i=0; i<n; ++i) {
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
f[i] = {a,b,c};
}
vector<LL> res;
for(int i=0; i<n; ++i) {
pq.push({f[i].get(1), i});
p[i] = 1;
}
while (res.size() < m) {
auto t = pq.top();
pq.pop();
res.push_back(t.v);
int& pp = p[t.id];
pp++;
pq.push({f[t.id].get(pp), t.id});
}
for(int i=0; i<m; ++i) {
printf("%lld ", res[i]);
}
return 0;
}
链接：https://www.dianjilingqu.com/478659.html
