最小函数值

GitHub跳转原题关系图返回列表

把每个递增二次函数看成有序序列，用堆做 n 路归并取前 m 项。

OJ: luogu

题目 ID: P2085

难度:普及/提高-

标签:多路归并二叉堆python

日期: 2026-07-16 21:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

给出多个在正整数域递增的二次函数，输出所有函数值合并后的前 m 小。

思路

每个函数产生 F(1),F(2),... 一条有序序列。堆中先放每条序列第一项；弹出 (value,function,x) 后，输出它并压入同函数的 x+1，就是标准多路归并。

Python 知识

  • 堆元组自动按函数值优先排序，并用后续字段稳定打破平局。
  • 局部 value(function, x) 集中表达二次式。
  • print(*answers) 直接空格分隔输出。

代码

python
import heapq
import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
n, required = next(data), next(data)
functions = [(next(data), next(data), next(data)) for _ in range(n)]


def value(function, x):
    a, b, c = functions[function]
    return a * x * x + b * x + c


heap = [(value(i, 1), i, 1) for i in range(n)]
heapq.heapify(heap)
answers = []
for _ in range(required):
    result, function, x = heapq.heappop(heap)
    answers.append(str(result))
    x += 1
    heapq.heappush(heap, (value(function, x), function, x))
print(*answers)

复杂度

时间 O((n+m)log⁡n)O((n+m)\log n)，空间 O(n+m)O(n+m)（含答案）。

总结

看到许多单调序列的全局前若干小值，应优先想到“每路只保留当前头”的堆归并。