【题解-信息学奥赛一本通】1370：最小函数值(minval)

题目1370最小函数值(minval)题目描述有n个函数分别为F 1 , F 2 , . . . , F n F_1,F_2,...,F_nF1​,F2​,...,Fn​。定义F i ( x ) A i x 2 B i x C i ( x ∈ N ∗ ) F_i(x)A_ix^2B_ixC_i(x∈N∗)Fi​(x)Ai​x2Bi​xCi​(x∈N∗)。给定这些A i 、 B i 和 C i A_i、B_i和C_iAi​、Bi​和Ci​请求出所有函数的所有函数值中最小的m个如有重复的要输出多个。输入第一行输入两个正整数n和m。以下n行每行三个正整数其中第i行的三个数分别位A i 、 B i 和 C i A_i、B_i和C_iAi​、Bi​和Ci​。输入数据保证A i 10 B i 100 C i 10000 A_i10B_i100C_i10000Ai​10Bi​100Ci​10000。输出将这n个函数所有可以生成的函数值排序后的前m个元素。这m个数应该输出到一行用空格隔开。时空限制1s / 64MB样例输入3 10 4 5 3 3 4 5 1 7 1样例输出9 12 12 19 25 29 31 44 45 54提示【数据规模】n,m≤10000。代码#includebits/stdc.husingnamespacestd;typedefpairint,intPII;constintN1000010;intn,m,k,x[N];structnode{inta,b,c;}w[N];priority_queuePII,vectorPII,greaterPIIheap;intmain(){cinnm;for(inti0;in;i){cinw[i].aw[i].bw[i].c;heap.push({w[i].aw[i].bw[i].c,i});x[i]1;}k0;while(!heap.empty()km){PII theap.top();heap.pop();coutt.first ;intit.second;x[i];intaw[i].a,bw[i].b,cw[i].c;heap.push({a*x[i]*x[i]b*x[i]c,i});k;}return0;}结果