最小函数值 二叉堆
问题描述
有n个函数，分别为F1,F2,...,Fn。定义Fi(x)=Ai×x2+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个数应该输出到一行，用空格隔开。
样例输入
3 10 4 5 3 3 4 5 1 7 1样例输出
9 12 12 19 25 29 31 44 45 54限制与约定
n,m<=10 000
时间限制：1s
空间限制：128MB
#include<cstdio> #include<cmath> #include<algorithm> #include<iostream> using namespace std; struct fac {int a,b,c;int x;int num; }; fac mr[10005]; int js(int a,int b,int c,int x) {return a*x*x+b*x+c; } void td(int i,int n) {int j;while(i*2<=n){j=2*i;if(j+1<=n && mr[j].num>mr[j+1].num) j++;if(mr[i].num>mr[j].num) {swap(mr[i],mr[j]);i=j;}else break;}return; } int n,m; int main() {scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){scanf("%d%d%d",&mr[i].a,&mr[i].b,&mr[i].c);mr[i].x=1;mr[i].num=js(mr[i].a,mr[i].b,mr[i].c,1);}for(int i=n/2;i>=1;i--) td(i,n);for(int i=1;i<=m;i++){printf("%d ",mr[1].num);mr[1].x++;mr[1].num=js(mr[1].a,mr[1].b,mr[1].c,mr[1].x);td(1,n);}return 0; }
转载于:https://www.cnblogs.com/hfang/p/11239983.html
总结
