题目描述
有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<=10000。
输出格式
输出将这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
#include <bits/stdc++.h>
using namespace std;
int m, n;
int a[10001], b[10001], c[10001], x[10001], d[10001], p[10001];
int xx, t = 0;
int f(int a, int b, int c, int x){
return (a * x * x + b * x + c);
}
void up(int x, int y){
int i, j, q;
t++;
d[t] = x;
p[t] = y;
i = t;
while(i > 1){
j = i / 2;
if(d[j] > d[i]){
q = d[j];
d[j] = d[i];
d[i] = q;
q = p[i];
p[i] = p[j];
p[j] = q;
}
i = j;
}
}
void down(){
int i, j, q;
i = 1;
while(i < t){
j = i * 2;
if(d[j + 1] < d[j] && j + 1 <= t){
j++;
}
if(j > t){
return;
}
if(d[j] < d[i]){
q = d[j];
d[j] = d[i];
d[i] = q;
q = p[i];
p[i] = p[j];
p[j] = q;
}
i = j;
}
}
int main(){
scanf("%d%d", &n, &m);
memset(d, 0, sizeof(d));
for(int i = 1; i <= n; i++){
scanf("%d%d%d", &a[i], &b[i], &c[i]);
x[i] = 1;
xx = f(a[i], b[i], c[i], x[i]);
up(xx, i);
}
for(int i = 1; i <= m; i++){
printf("%d ", d[1]);
x[p[1]] = x[p[1]] + 1;
d[1] = f(a[p[1]], b[p[1]], c[p[1]], x[p[1]]);
down();
}
}