题目描述
有n个函数，分别为F1,F2,...,Fn。定义Fi(x)=Ai*x^2+Bi*x+Ci (x∈N*)。给定这些Ai、Bi和Ci，请求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。
输入输出格式
输入格式：
输入数据：第一行输入两个正整数n和m。以下n行每行三个正整数，其中第i行的三个数分别位Ai、Bi和Ci。Ai<=10，Bi<=100，Ci<=10 000。
输出格式：
输出数据：输出将这n个函数所有可以生成的函数值排序后的前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
说明
数据规模：n,m<=10000
解析：
思路很简单，跟那道P1631 序列合并基本上一个思路，我们可以把每个函数看成一个单调递增序列，用堆实现和这题相似的做法。
相当于一个动态的比较问题吧，所以用堆更好实现，所以实际上没有分支问题，比P1631 序列合并这道题简单。
然而我还是不会用STL，借鉴了一下题解。。。
参考代码：
#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<algorithm> #include<queue> #define N 10010 using namespace std; int n,m; struct fun{int a,b,c; }f[N]; struct value{int num,x,val; }r[N]; priority_queue<value,vector<value>,greater<value> > q; bool operator>(value a,value b){//我还是不会重载运算符return a.val>b.val; } int func(int a,int b,int c,int x) {return a*x*x+b*x+c; } void solve() {for(int i=1;i<=n;i++) q.push((value){i,1,func(f[i].a,f[i].b,f[i].c,1)});for(int i=1;i<=m;i++){value x=q.top();q.pop();printf("%d ",x.val);q.push((value){x.num,x.x+1,func(f[x.num].a,f[x.num].b,f[x.num].c,x.x+1)});} } int main() {int a,b,c;cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].c);solve();return 0; }
2019-05-20 20:30:02