题解

这个问题的目标是最小化一个描述堆肥运输总成本的函数 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)，并跟踪它达到的最小值。

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
     
int N;
map<int,int> slopechg;   
     
int main(void)
{
   long long current_f = 0, slope_f = 0, current_y = -2000000000;

   cin >> N;
   for (int i=0; i<N; i++) {
      int a, b;
      cin >> a >> b;
      current_f += abs(a-b);  
      if (abs(a) > abs(a-b)) continue;
      slopechg[b]+=2;
      if (a<b && a<0)   { slopechg[0]--; slopechg[2*b]--; }
      if (a<b && a>=0)  { slopechg[2*b-2*a]--; slopechg[2*a]--; }
      if (a>=b && a<0)  { slopechg[2*b-2*a]--; slopechg[2*a]--; }
      if (a>=b && a>=0) { slopechg[0]--; slopechg[2*b]--; }
   }      
   long long min_f = current_f;
   for (auto p : slopechg) {
      int new_y = p.first, delta_slope = p.second;
      current_f += slope_f * (new_y - current_y);
      current_y = new_y;
      slope_f += delta_slope;
      min_f = min(min_f, current_f);
   }

   cout << min_f << "\n";
   return 0;
}