1 条题解
-
-1
思路
- 枚举x，根据输入的a,b,c，把生成的计算结果加入到优先队列中，取出最小的 m 个。
- 枚举 x 时，对于每一组a,b,c我们只需要生成 m 个结果加入优先队列就足够了。
- 常规思路是定义数值越小优先级越高，最后出队m个数，但是这种方法需要定义一个容量很大的优先队列，因此可以转换一下思路，定义数值越大优先级越高，将第1组a,b,c生成的m个结果先入队，从第组a,b,c生成结果开始，进行一个打擂法优化，如果新生成的数 小于 q.top()，那么就可以把新生成的数入队，并弹出队列中最大的数，继续操作，如果新生成的数 大于等于 q.top（），直接break掉，输入下一组a,b,c继续操作，因为a,b,c,x都是正数，所以生成的数肯定是越来越大，如果当前生成的数，比优先队列中最大的数还要大，那就没必要继续往后生成数了。
参考代码
for(int i = 1; i <= n; i++) { cin >> a >> b >> c; for (int x = 1; x <= m; x++) { int fx; fx = a * x * x + b * x + c;//k为函数值y if (i==1) q.push(fx); else { if(fx < q.top()) { q.push(fx); q.pop(); } else break; //如果fx已经大于队首了，接下来fx仍旧单调递增,可以直接break掉，一个重要的优化 } } }
董一骏
MOD
@ 2024-4-20 16:00:13
- 1