1370：最小函数值(minval)
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
有n个函数，分别为F1,F2,...,Fn。定义Fi(x)=Aix^2+Bix+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≤10000。
1. #include <iostream> 2. #include <cstdio> 3. #include <algorithm> 4. using namespace std; 5. int len,maxl,maxx,n,m,xx,yy,zz; 6. struct student{ 7. int a,b,c,x,y; 8. }; 9. student tree[100001],z; 10. int cmp(const student &a,const student &b){ 11. if(a.y<b.y) return 1; 12. return 0; 13. } 14. void put(student zz){ 15. len++; 16. tree[len]=zz; 17. tree[len].y=tree[len].a*tree[len].x*tree[len].x+tree[len].b*tree[len].x+tree[len].c; 18. int son=len; 19. while(son>1){ 20. int fa=son/2; 21. if(tree[son].y>=tree[fa].y) return; 22. swap(tree[son],tree[fa]); 23. son=fa; 24. } 25. } 26. void get(){ 27. z=tree[1]; 28. cout<<tree[1].y<<" "; 29. tree[1]=tree[len--]; 30. int fa=1; 31. while(fa*2<=len){ 32. int son=fa*2; 33. if(son+1<=len && tree[son].y>tree[son+1].y) son++; 34. if(tree[son].y>=tree[fa].y) break; 35. swap(tree[son],tree[fa]); 36. fa=son; 37. } 38. z.x++; 39. put(z); 40. } 41. int main() 42. { 43. cin>>n>>m; 44. for(int i=1;i<=n;i++){ 45. student s; 46. cin>>s.a>>s.b>>s.c; 47. s.x=1; 48. s.y=s.a*s.x*s.x+s.b*s.x+s.c; 49. put(s); 50. } 51. for(int i=1;i<=m;i++) get(); 52. return 0; 53. }
