自动搬运

查看原文

来自洛谷，原作者为

	Euler_Pursuer 如果命运是块顽石，我就化为大锤，将它砸得粉碎！

搬运于2025-08-24 21:33:49，当前版本为作者最后更新于2017-12-09 20:35:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

点击查看题目来源

Solution

该题目给定了我们一些二次函数，不过这个函数只取了横坐标为正整数部分的值，并且三个系数都为正数，通过代数证明或者图像对称轴分析，都可以肯定，该函数在其定义域（正整数）上，单调递增且恒大于0。

接下来我们再看到题目要求，求这些函数所生成的所有函数值中最小的m个。

暴力求解法

比较暴力的方法是从1开始循环（可能不是最暴力的方法），将1代入所有的函数中，分别得到n个函数值，然后再循环到2，按照这样的方法再来一遍，又有n个函数值，又因为这些都是在其定义域内单调递增的函数，那么首先可以确定1中所有小于等于2中最小函数值的函数值，然后接着按照上述方案做，循环到k时，可以确定从x=1到x=k-1中所有小于等于x=k中最小函数值的函数值，直到确定了m个值。

但是这样的话，思想实在简单，绝配暴力算法一名。暴力之处在于：一、每次求出$O(n)$的函数值，耗费$O(n)$的空间，最坏情况下要求$O(mn)$次，花费$O(mn)$空间，而数据一大，时间空间无疑是要超出范围的；二、每次循环求出的函数值得进行排序，如果不排序，那个运算量不敢恭维，假设使用$\Theta (nlgn)$复杂度排序，那么也需要花$\Theta (mnlgn)$的复杂度；三、再加上每次需要计算x=k中的最小函数值与前面k-1中所有的函数值进行比较，这样在最坏情况下将花费$O(\sum ^{m-1} _{k=0} (kn))=O((m-1)mn/2)=O(m^2n)$的时间代价。

那么，总的算来，就会消耗$O(O(mn)+\Theta (mnlgn)+O(m^2n))=O(m^2n)$的时间代价，极其暴力！而且空间上的消耗也是巨大的！

那么，我们该如何优化呢？

优化的思想

其实，大家看到函数解析式极其定义域就不难知道，他实际上是给了我们n串排好序的数组，只是每个数组中下标与其值存在一定的对应关系。我们由上面所说的可知，对于每个数组，它们的最小值所在的下标都是1。现在，我们可以想象一下，每个数组都有一个箭头，每个箭头都指向1，然后在所有箭头指向的函数值中，找到最小的那个，此时已经找到了1个最小函数值。接着，刚才输出来的值所对应的箭头就要向后移，指向x=2，然后再去和其他箭头指向的函数值比较，以此类推。下面的两个图形象地展现了一部分操作过程。

那么，现在我们需要将文字描述转化为程序思路。

首先我们需要用三个数组存A、B、C的值，然后需要一个cmin存当前最小值，最后只需要拿一个数组F来表示每个函数中的那个“箭头”所指的位置，那么箭头所指的函数值就会是$A[k]F[k]^2+B[k]F[k]+C[k]$，至此，思路就很明了了。

下面是我写的程序，很简单，最长耗时测试点用了344ms，没超时。

    #include <iostream>
    using namespace std;
    int main()
    {
        int n,m,i,j,cmin,jmin;
        int A[10010], B[10010], C[10010];
        int F[10010];
        cin>>n>>m;
        for(i=0;i<n;i++)
        {
            cin>>A[i]>>B[i]>>C[i];
            F[i]=1;
        }
        for(i=0;i<m;i++)
        {
            cmin=100000000;
            for(j=0;j<n;j++)
            {
                if(A[j]*F[j]*F[j]+B[j]*F[j]+C[j]<cmin)
                {
                    cmin=A[j]*F[j]*F[j]+B[j]*F[j]+C[j];
                    jmin=j;
                }
            }
            cout<<A[jmin]*F[jmin]*F[jmin]+B[jmin]*F[jmin]+C[jmin]<<' ';
            F[jmin]++;
        }
        return 0;
    }

该程序的时间复杂度为$\Theta (mn)$。 大家也许会发现，这里每次都重复计算了很多函数的值，浪费了很多时间，那有没有办法针对这一问题进行优化呢？答案是肯定的。

更优化的解法

对于上述问题的优化方法，比较好的是用堆来做。思路是这样的：首先，我们可以在所有“箭头”指向1的时候，对所有箭头对应的函数值建立小根堆；然后，每次从堆顶取走那个数，并将其所对应的“箭头”指向下一个函数值，然后把这个新的函数值代替那个取走的函数值放在堆顶，并自顶向下维护堆（大家可以证明一下，一直这样操作下去，堆的性质恒成立）。下面是我的参考程序：

    #include <iostream>
    using namespace std;
    struct DUI
    {
        int val;//箭头表示的函数值
        int x;//每个函数都有被输入进来的先后顺序，这个是第x个输入进来的函数
        //因为堆里面的节点总是在变化的，所以我们要记录哪个函数在哪个位置
    }a[10010];
    int heap_size;//堆的大小
    void CHANGE(int m, int n)//自己写的交换函数
    {
        int t;
        t=a[m].val;
        a[m].val=a[n].val;
        a[n].val=t;
        t=a[m].x;
        a[m].x=a[n].x;
        a[n].x=t;
    }
    void MIN_HEAPIFY(int i)
    {
        int l=i*2;//右子节点
        int r=i*2+1;//左子节点
        int smallest;//记录父子节点值最小的那个
        if(l<=heap_size&&a[l].val<a[i].val)
            smallest=l;
        else
            smallest=i;
        if(r<=heap_size&&a[r].val<a[smallest].val)
            smallest=r;//父子节点中值最小的位置
        if(smallest!=i)//父节点最大则不变
        {
            CHANGE(i,smallest);//子节点大则交换父子节点
            MIN_HEAPIFY(smallest);//交换后继续往下维护
        }
    }
    void BUILD_HEAP()//建立小根堆
    {
        int i;
        for(i=heap_size/2;i>0;i--)
            MIN_HEAPIFY(i);//自底向上建堆
    }
    int main()
    {
        int n,m,i,j;
        int A[10010], B[10010], C[10010];
        int F[10010];//每个函数的"箭头"位置
        cin>>n>>m;
        for(i=1;i<=n;i++)
        {
            cin>>A[i]>>B[i]>>C[i];
            F[i]=1;
            a[i].val=A[i]*F[i]*F[i]+B[i]*F[i]+C[i];
            a[i].x=i;//输入的顺序，第i个被输进来的
        }
        heap_size=n;
        BUILD_HEAP();
        for(i=0;i<m;i++)
        {
            cout<<a[1].val<<' ';//输出最小函数值
            F[a[1].x]++;//它所在的函数中的"箭头"往后移
            a[1].val=A[a[1].x]*F[a[1].x]*F[a[1].x]+B[a[1].x]*F[a[1].x]+C[a[1].x];//"箭头"变则值变
            MIN_HEAPIFY(1);//自顶向下维护堆
        }
        return 0;
    }

该程序的时间复杂度为$\Theta (nlgn)$或$\Theta (mlgn)$。程序在洛谷上测试通过了，并且最大耗时的测试点耗时8ms。

→注

• 这里涉及到的堆的操作的方法来自《算法导论》。

• 如果有什么错误可以向本人提出，我会做出及时更正。

写在最后

感谢大家的关注和阅读。

本文章借鉴了少许思路，但总体为本人原创，如需转载，请注明出处。