原题链接:https://www.luogu.com.cn/problem/P2085
题意解读:有n个函数,函数中x取值>=1,计算所有函数能得到的值中最小的m个。
解题思路:
函数中x取值是>=1的整数,因此每个函数的值是f(1),f(2),f(3)....,是一个递增序列,题目本质上是要从n个递增序列中找到前m个最小的数。
首先,对所有函数计算f(1),放入优先队列,最小值一定在其中。
第二小的值如何计算?可以将最小的f(1)弹出,计算相应的f(2),再放回优先队列,再取此时最小值,即可得到第二小的值。
第三、四。。。m小的值计算方法以此类推。
用算法的语言描述:
1、初始计算所有函数在x=1时的值
2、取最小值
3、然后将最小值对应的函数x+1再计算函数值
4、重复2,直到取m次最小值
由于优先队列要记录函数值,取得函数值时x的值,以及第几个函数,因此可以定义结构体
struct Node
{
int val, idx, x; //val函数值,idx函数编号,x未知数取值
bool operator < (const Node &node) const &
{
if(val != node.val) return val > node.val;
if(x != node.x) return x > node.x;
return idx > node.idx;
}
};
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
struct Node
{
int val, idx, x; //val函数值,idx函数编号,x未知数取值
bool operator < (const Node &node) const &
{
if(val != node.val) return val > node.val;
if(x != node.x) return x > node.x;
return idx > node.idx;
}
};
int n, m;
int a[N], b[N], c[N];
priority_queue<Node> q;
int f(int idx, int x)
{
return a[idx] * x * x + b[idx] * x + c[idx];
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i] >> b[i] >> c[i];
q.push({f(i, 1), i, 1});
}
while(m--)
{
Node p = q.top(); q.pop();
cout << p.val << " ";
q.push({f(p.idx, p.x + 1), p.idx, p.x + 1});
}
return 0;
}
标签:node,return,idx,val,int,洛谷题,二叉,P2085,函数 From: https://www.cnblogs.com/jcwy/p/18539897