[洛谷P2085]最小函数值

题目大意：有n个函数，分别为F1,F2,...,Fn。定义Fi(x)=Ai*x^2+Bi*x+Ci (x∈N*)。给定这些Ai、Bi和Ci，要求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。

解题思路：因为$n,m\leq 10000$，暴力枚举肯定是不可取的。我们发现，Fi(x)一定不会大于Fi(x+1)，那么我们可以把所有Fi(1)放进一个小根堆里，每次取出一个Fi(x)，就把Fi(x+1)放进去，这样就能保证答案从小到大。时间复杂度为$O(m\log n)$。

C++ Code：

#include<cstdio>

#include<ext/pb_ds/priority_queue.hpp>

using namespace __gnu_pbds;

struct heapnode{

	int num,x;long long ans;

	bool operator<(const heapnode&$)const{return ans>$.ans;}

};

priority_queue<heapnode>q;

int n,m,a[10005],b[10005],c[10005];

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i){

		scanf("%d%d%d",&a[i],&b[i],&c[i]);

		q.push((heapnode){i,1,(long long)a[i]+b[i]+c[i]});

	}

	bool space=false;

	while(m--){

		heapnode p=q.top();q.pop();

		if(space)putchar(' ');else space=true;

		printf("%lld",p.ans);

		++p.x;

		p.ans=a[p.num]*p.x*p.x+b[p.num]*p.x+c[p.num];

		q.push(p);

	}

	puts("");

	return 0;

}