首页 > 代码库 > ?Luogu P2085 最小函数值
?Luogu P2085 最小函数值
P2085 最小函数值
题目描述
有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 104 5 33 4 51 7 1
输出样例#1：
9 12 12 19 25 29 31 44 45 54
说明
数据规模：n,m<=10000
Solution
//先计算出x=1时候的情况存Heap里
//然后每次找最小时，插入当前的最小的所属的函数f[i](x+1)到root ，然后维护小根堆
（为什么？根据不等式的性质if a<b then a*c<b*c while c>0）
//w记录当前的函数最大的x
//name[i]表示第I个节点的是第几个函数
//insert插入一个新元素到堆，然后维护堆的性质，这里是维护小根堆
//get得到当前最小值就是root，然后删掉把最后的一个元素作为root然后维护小根堆
1 program wonder; 2 const 3 inf=‘minval.in‘; 4 outf=‘minval.out‘; 5 var 6 len,i,j,n,tmp,ans,m:longint; 7 heap,w,a,b,c,name:array[0..10000] of longint; 8 9 procedure swap(var aa,bb:longint);10 var t:longint;11 begin12 t:=aa; aa:=bb; bb:=t;13 end;14 15 procedure insert(tmp:longint);16 var17 i:longint;18 begin19 inc(len);20 heap[len]:=tmp; name[len]:=len;21 i:=len;22 while (i>1) and (heap[i div 2]>heap[i]) do23 begin24 swap(heap[i],heap[i div 2]);25 swap(name[i],name[i div 2]);26 i:=i div 2;27 end;28 end;29 30 procedure ch;31 var32 dad,son:longint;33 stop:boolean;34 begin35 write(heap[1],‘ ‘);36 inc(w[name[1]]);37 heap[1]:=w[name[1]]*w[name[1]]*a[name[1]]+w[name[1]]*b[name[1]]+c[name[1]];38 dad:=1;39 stop:=false;40 while ((dad*2+1<=len) or (dad*2<=len)) and (not stop) do41 begin42 if (heap[dad*2+1]>heap[dad*2]) or (dad*2+1>len) then43 son:=dad*244 else son:=dad*2+1;45 if heap[dad]<=heap[son] then stop:=true46 else begin47 swap(heap[dad],heap[son]);48 swap(name[dad],name[son]);49 dad:=son; //!!!!50 end;51 end;52 end;53 54 begin55 assign(input,inf); assign(output,outf);56 reset(input); rewrite(output);57 58 readln(n,m);59 for i:= 1 to n do60 begin61 read(a[i],b[i],c[i]);62 tmp:=a[i]+b[i]+c[i];63 w[i]:=1;64 insert(tmp);65 end;66 67 for i:= 1 to m do ch;68 69 close(input); close(output);70 end.
?Luogu P2085 最小函数值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。