SSL 1411 最小函数值_优先队列

发布于 2019-04-20  11 次阅读


题目大意

在n个函数中找出前m小的函数值

思路

先将第一个函数的前m个加入队列中,然后枚举其他函数,如果当前x得出的值已经比队头大的话可以直接break
这里每找到一个比队头小的数时都要将队头弹出
O(nmlogm) 但实际小得多

#include 
#include 
using namespace std;
priority_queue heap;
long long a[10100][4],f[10000];
int main()
{
    long long n,m;
    scanf("%I64d%I64d",&n,&m);
    for (long long i=1;i<=n;i++)
    {
        scanf("%I64d%I64d%I64d",&a[i][1],&a[i][2],&a[i][3]);
    }
    for (long long i=1;i<=m;i++)
    {
        long long x=a[1][1]*i*i+a[1][2]*i+a[1][3];
        heap.push(x);
    }
    for (long long i=2;i<=n;i++)
    {
        for (long long j=1;j<=m;j++)
        {
            long long x=a[i][1]*j*j+a[i][2]*j+a[i][3];
            if (x
]]>