最小函数值(minval)（信息学奥赛一本通- P1370）

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

第一行输入两个正整数n和m。

以下n行每行三个正整数，其中第i行的三个数分别位Ai、Bi和Ci。输入数据保证Ai<=10，Bi<=100，Ci<=10000。

将这n个函数所有可以生成的函数值排序后的前m个元素。这m个数应该输出到一行，用空格隔开。

【数据规模】

n,m≤10000。

1. 解题思路分析

本题的核心目标是从 n 个二次函数生成的无数个值中，筛选出最小的 m 个数。由于 m 远小于可能产生的数据总量，直接计算所有值并排序（O(N⋅Mlog(NM))）显然不够高效。我们采用了“维护固定大小集合”的策略。

数据结构选择：大根堆

虽然题目要求的是“最小”的数，但在维护一个容量为 m 的候选集合时，我们需要使用大根堆（priority_queue默认大根堆）。

• 理由：我们要时刻知道当前选出的 m 个数中，最大的那个数是多少（即堆顶元素）。

• 作用：堆顶元素是当前候选集合的“门槛”。对于一个新计算出的函数值，只有当它小于堆顶时，它才有资格进入前 m 名。此时我们将堆顶弹出（淘汰当前第 m 小），将新值压入。

关键优化：利用函数单调性

题目给定 A,B,C 均为正整数，因此二次函数 f(x)=A*x^2+B*x+C 在 x≥1 的区间上是单调递增的。 这一性质对于优化算法至关重要：

• 在遍历某一组参数 (A,B,C) 时，我们让 x 从 1 开始递增。

• 如果当前计算出的 f(x) 已经大于或等于堆顶元素，由于函数的单调递增性，后续的 f(x+1),f(x+2)... 必然也大于堆顶。

• 结论：此时无需继续计算该函数的后续值，直接break跳出当前循环，处理下一组函数。这一剪枝操作保证了算法不会超时。

2. 算法流程总结

1. 初始化：读取第一组函数参数，计算前 m 个值推入优先队列，建立初始的“最小m数”集合。

2. 动态更新：

   • 依次读取后续 n−1 组函数参数。

   • 对于每组函数，从 x=1 开始计算。

   • 若 f(x)<q.top()：说明找到了更优解，执行pop()和push(f(x))。

   • 若 f(x)≥q.top()：触发单调性剪枝，直接break。

3. 结果输出：由于大根堆弹出顺序是从大到小，需要将元素暂存入数组，最后倒序输出以满足题目从小到大的要求。

3. 实现细节与注意事项

• 数据范围由于涉及到 x^2 的运算，函数值可能会超过int范围，因此优先队列和中间变量必须使用long long。

• 输出数组类型：代码中用于倒序输出的数组h应定义为long long以匹配优先队列的数据类型。

• 时间复杂度：在最坏情况下（剪枝未频繁触发），每次堆操作为 O(logm)。由于单调性的存在，实际交换次数远小于理论上限，整体效率足以通过测试点。

//思路：先通过第一组abc算出x（1-m）的m个f值存入优先队列（最大堆），后面每一组都通过与堆顶 //进行比较，如果小于堆顶就存进去，直到大于堆顶就开始下一组，最后堆里存放的一定是最小的m个数，输出即可 #include <iostream> #include <queue> using namespace std; int a,b,c; priority_queue<long long> q;//最大堆 long long f(int x,int a,int b,int c){ return a*x*x+b*x+c; } int main(){ int n,m; cin>>n>>m; //第一组数据先存入优先队列 cin>>a>>b>>c; for(int i=1;i<=m;i++){ long long tmp=f(i,a,b,c); q.push(tmp); } for(int i=2;i<=n;i++){//从第二组开始比较 cin>>a>>b>>c; for(int j=1;j<=m;j++){ long long tmp=f(j,a,b,c); if(tmp<q.top()){//tmp比堆里的最大值要小，就弹出堆顶，然后存入tmp q.pop(); q.push(tmp); } else{//i组当前j的情况下tmp已经大于堆顶（即堆里的最大值），就不需要让j继续增加了，可以比较下一组了 break; } } } //因为要从小到大输出，那就把堆先存进一个数组再输出 long long h[10001]; int cnt=0;//存进多少个数； while(!q.empty()){ h[++cnt]=q.top(); q.pop(); } for(int i=cnt;i>=1;i--) cout<<h[i]<<" "; return 0; }