【题目描述】

　　　　有n个函数，分别为F1,F2,...,FnF1,F2,...,Fn。定义Fi(x)=Aix²+Bix+Ci(x∈N∗)。给定这些Ai、Bi、Bi和Ci，请求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。

【题目链接】

　　　　http://ybt.ssoier.cn:8088/problem_show.php?pid=1370

【算法】

　　　　大根堆记录，一旦总个数超过m个则删去堆顶。

【代码】

1 #include 
     
       2 using namespace std; 3 int n,m,i,a,b,c,j; 4 int heap[10010],tot; 5 int calc(int a,int b,int c,int x) { return a*x*x+b*x+c; } 6 void up(int p) 7 { 8     while(p>1) 9         if(heap[p]>heap[p/2]) swap(heap[p],heap[p/2]),p/=2;10         else break;11 }12 void Insert(int val)13 {14     heap[++tot]=val;15     up(tot);16 }17 void down(int p)18 {19     int s=p*2;20     while(s<=tot) {21         if(s
      
       heap[s]) s++;22         if(heap[s]>heap[p]) swap(heap[s],heap[p]),p=s,s*=2;23         else break;24     }25 }26 void Extract()27 {28     heap[1]=heap[tot--];29     down(1);30 }31 void print()32 {33     int cur=heap[1];34     if(tot>1) Extract(),print(),printf(" %d",cur);35     else if(tot==1) printf("%d",cur);36 }37 int main()38 {39     scanf("%d%d",&n,&m);40     for(i=1;i<=n;i++) {41         scanf("%d%d%d",&a,&b,&c);42         for(j=1;j<=m;j++) {43             int cur=calc(a,b,c,j);44             if(tot
       
        =heap[1]) break;46             else Extract(),Insert(cur);47         }48     }49     print();50     return 0;51 }