CJOJ 2484 函数最小值 / Luogu 2085 函数最小值（STL优先队列，堆）
Description
有n个函数，分别为F1,F2,...,Fn。定义 \(Fi(x)=Aix^2+Bix+Ci(x∈N^∗)\)。给定这些Ai、Bi和Ci，请求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。
第一行输入两个正整数n和m，n<=500000, m<=500000 以下n行每行三个正整数，其中第i行的三个数分别为Ai、Bi和Ci。输入数据保证Ai<=10，Bi<=100，Ci<=10000。
Output
输出将这n个函数所有可以生成的函数值排序后的前m个元素。 这m个数应该输出到一行，用空格隔开，并且最后一个数右侧也有一个空格。
3 10 4 5 3 3 4 5 1 7 1
Sample Output
9 12 12 19 25 29 31 44 45 54
Http
CJOJ:http://oj.changjun.com.cn/problem/detail/pid/2484 Luogu:https://www.luogu.org/problem/show?pid=2085
Source
STL优先队列 堆
题目大意
有n个二次函数，均满足\(Fi(x)=Aix^2+Bix+Ci\)，x为正整数，a,b,c均为大于等于0的数，求所有函数的所有函数值中最小的m个，如果有重复则要输出多个
解决思路
想要做出这道题目，首先你要有基础的二次函数知识。 观察题目中的各个值的范围，首先因为a,b,c>0，所以这些二次函数都满足开口向上且对称轴在x轴负半轴。那么我们就可以知道Fi(1)一定是第i个函数的最小值，那么我们把所有的Fi(1)加入一个优先队列(小的优先)，每次取出对首元素输出，在把队首元素所对应的的函数的下一个值放入优先队列，循环m次就可以了。（是不是有一点像spfa算法呢？）
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
class Function//存下每一个函数的三个参数的值
{
public:
long long a,b,c;
};
class Value//优先队列中存取的元素
{
public:
long long data,num,x;//data表示是第num个函数在自变量取x时候的值 即data=Fnum(x)
};
bool operator < (Value a,Value b)//重载小于号（优先队列中要用），注意是相反的
{
return a.data>b.data;
}
const int maxN=500000;
int n,m;
priority_queue<Value> Q;
Function F[maxN];
long long solve(long long num,long long x);//计算Fnum(x)的值
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
cin>>F[i].a>>F[i].b>>F[i].c;
Q.push((Value){solve(i,1),i,1});//将初始的每个Fi(1)都放入优先队列
}
for (int i=1;i<=m;i++)
{
Value x=Q.top();//取出队首元素并输出
Q.pop();
cout<<x.data<<' ';
Q.push((Value){solve(x.num,x.x+1),x.num,x.x+1});//将队首元素对应的函数的下一个值放入优先队列
}
return 0;
}
long long solve(long long num,long long x)
{
return F[num].a*x*x+F[num].b*x+F[num].c;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7137707.html
相关资源：JAVA上百实例源码以及开源项目
