这个问题的目标是最小化一个描述堆肥运输总成本的函数 f(y)，其中 y 表示传送门的端点位置。由于 f(y) 具有分段线性结构，我们通过正向扫描 y 并沿着 f(y) 进行追踪，在每个断点处暂停以适当方式调整 f(y) 的当前斜率，并在此过程中保持运行时最小值。只有 O(N) 个断点，因此在将它们在 O(NlogN) 时间内排序后，我们只需要在 O(N) 时间内扫描并追踪 f(y)。 尽管上面的高级算法框架相对简单，但需要一些数学上的努力来确定 f(y) 中所有断点的位置 -- 也就是说，在哪个 y 值处以及在每个断点处斜率如何改变。注意，总运输距离 f(y) 可以分解为每个堆 i 的运输距离， f(y)=∑Ni=1fi(y) ， 其中 fi(y)=min(|ai−bi|,|ai−0|+|bi−y|) 表示仅用于运输堆 i 的成本（第一部分表示直接移动的运输成本，第二部分表示传送的成本）。每个 fi 都是关于 y 的相对简单的函数。经过一些数学推理，我们可以推断出 fi 具有以下形状： 就断点而言，这些函数对 f(y) 有所贡献。例如，如果 |ai|≥|ai−bi|，则 fi(y) 中根本没有断点 -- fi(y) 的整个贡献就是将 f(y) 上移 |ai−bi|。在另一个例子中，如果 ai<0 并且 ai≥bi，则 fi 具有三个断点，它们对 f(y) 有所贡献：在 y=0 处，fi(y)（因此也是 f 的斜率）减小 1， 在 y=b 处增加 2，在 y=2b 处减小 1。 我的代码使用vector来存储 f 的所有不同断点处的斜率变化，然后按 y 的排序顺序扫描这些斜率变化，简单地追踪 f(y)，并跟踪它达到的最小值。