我的思考——最小函数值

[点击查看题目来源](https://www.luogu.org/problemnew/show/2085) ## 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，没超时。 ```cpp #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的时候，对所有箭头对应的函数值建立小根堆；然后，每次从堆顶取走那个数，并将其所对应的“箭头”指向下一个函数值，然后把这个新的函数值代替那个取走的函数值放在堆顶，并自顶向下维护堆（大家可以证明一下，一直这样操作下去，堆的性质恒成立）。下面是我的参考程序： ```cpp #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。 #### →注 - 这里涉及到的堆的操作的方法来自《算法导论》。 - 如果有什么错误可以向本人提出，我会做出及时更正。 #### 写在最后 感谢大家的关注和阅读。 本文章借鉴了少许思路，但总体为本人原创，如需转载，请注明出处。