蓝桥杯备考：堆算法之最小函数值
这道题暴力解法就是把所有函数的前m个值代入算出来，然后把每个前m值的数组都合并起来，前m个就是我们的结果，当然这种做法是会超时的
所以我们应该选择 优先级队列，我们代入1把所有的值加入优先级队列，每次输出最小值，并且把该序列的第二个数代入进去加进队列，直到输出m个数结束
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
ll a[N],b[N],c[N];
ll n,m;
ll calc(ll pos,ll num)
{
return a[pos]*num*num+b[pos]*num+c[pos];
}
struct node{
ll sum;//函数值
ll pos;//第i个函数
ll num;//代入值
bool operator< (const node& x) const
{
return sum > x.sum;
}
};
priority_queue<node> heap;
int main()
{
cin >> n >> m;
for(int i = 1;i<=n;i++)
{
cin >> a[i] >> b[i] >> c[i];
heap.push({calc(i,1),i,1});
}
for(int i = 1;i<=m;i++)
{
node t = heap.top();heap.pop();
ll sum = t.sum;ll num = t.num; ll pos = t.pos;
cout << sum << " ";
heap.push({calc(pos,num+1),pos,num+1});
}
return 0;
}