P2085 最小函数值

P2085

题目思路

因为系数都大于$0$，根据二次函数性质可知该函数在$(0,+\infty)$上单调递增。

于是对于$n$个方程，当$x=1$的时候函数值是最小的，从这些“最小值”中取出最小值并输出，然后将该函数的$x+1$，继续比较，这样一直找到$m$个就可以了。

该过程可用优先队列实现。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int A[N],B[N],C[N],f[N];
int n,m,jm;
int F(int x,int i)
{
    return A[i]*x*x+B[i]*x+C[i];
}
struct node{
    int val,id;
    node(){}
    node(int x,int y){val=x;id=y;}
};
bool operator<(const node &a,const node &b)
{
    return a.val>b.val;
}
priority_queue<node> q;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&A[i],&B[i],&C[i]),f[i]=1;//f存指针,x取值
    for(int i=1;i<=n;i++)
        q.push(node(F(f[i],i),i));
    for(int i=1;i<=m;i++)
    {
        node p=q.top();
        q.pop();
        f[p.id]++;
        q.push(node(F(f[p.id],p.id),p.id));
        printf("%d ",p.val);
    }
    return 0;
}

---