Description
有n个函数，分别为F1,F2,...,Fn。定义Fi(x)=Ai*x^2+Bi*x+Ci(x∈N*)。给定这些Ai、Bi和Ci，请求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。
Input
第一行输入两个正整数n和m。以下n行每行三个正整数，其中第i行的三个数分别位Ai、Bi和Ci。Ai<=10，Bi<=100，Ci<=10 000。
Output
输出将这n个函数所有可以生成的函数值排序后的前m个元素。这m个数应该输出到一行，用空格隔开。
Sample Input
3 10
4 5 3
3 4 5
1 7 1
Sample Output
9 12 12 19 25 29 31 44 45 54
Hint
n,m<=10,000
Thinking
首先根据二次函数的知识可以判断出，这里的每个函数在x>0范围内都是单调递增的。
可以根据堆的思想做这道题。开始时将每一个函数的第一个函数值加入小根堆，注意这里堆必须记录是第几个函数。每次取出堆顶元素加入到答案中，同时将堆顶元素所在的函数下标+1，将新得到的函数值加入堆中。重复以上步骤直到取出m个答案。
时间复杂度O(mlogn)
Code
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 7 struct func 8 { 9 int a,b,c,x; 10 }data[10050]; 11 struct node 12 { 13 int data,k; 14 friend bool operator >(const node &a,const node &b) {return a.data>b.data;} 15 friend bool operator <(const node &a,const node &b) {return a.data<b.data;} 16 //这两行用来自定义node类型的比较函数以便优先队列调用 17 }heap[10050]; 18 19 int n,m; 20 21 int t[10050]; 22 23 priority_queue<node,vector<node>,greater<node> > q; 24 int calc(int k) 25 { 26 int temp=0; 27 temp+=data[k].c; 28 temp+=data[k].b*data[k].x; 29 temp+=data[k].a*data[k].x*data[k].x; 30 data[k].x++; 31 return temp; 32 } 33 34 int main() 35 { 36 scanf("%d%d",&n,&m); 37 for(int i=1;i<=n;i++) 38 { 39 scanf("%d%d%d",&data[i].a,&data[i].b,&data[i].c); 40 data[i].x=1; 41 } 42 for(int i=1;i<=n;i++) 43 { 44 node temp; 45 temp.data=calc(i); 46 temp.k=i; 47 q.push(temp); 48 } 49 for(int i=1;i<m;i++) 50 { 51 printf("%d ",q.top().data); 52 int cc=q.top().k; 53 node temp; 54 temp.data=calc(cc); 55 temp.k=cc; 56 q.pop(); 57 q.push(temp); 58 } 59 printf("%d ",q.top().data); 60 return 0; 61 }