题目描述

Farmer John最讨厌的农活是运输牛粪。为了精简这个过程，他制造了一个伟大的发明：便便传送门！与使用拖拉机拖着装满牛粪的大车从一个地点到另一个地点相比，他可以使用便便传送门将牛粪从一个地点瞬间传送到另一个地点。

Farmer John的农场沿着一条长直道路而建，所以他农场上的每个地点都可以简单地用该地点在道路上的位置来表示（相当于数轴上的一个点）。一个传送门可以用两个数x和y表示，被拖到地点x的牛粪可以瞬间传送到地点y。

Farmer John决定建造一个起点位于x=0的传送门；你的任务是帮助他确定最佳的终点y。具体地说，在他的农场上有N堆牛粪（1≤N≤100,000）。第ii堆牛粪需要被从位置ai移动到位置bi，Farmer John会分别运输每一堆牛粪。我们设di为FJ使用拖拉机运输第i堆牛粪的距离，则当他直接使用拖拉机运输第i堆牛粪时，有di=|ai−bi|，或者di可能在他使用传送门的情况下可以变得更小（比方说，用他的拖拉机从ai运到x，再从y运到bi）。

请帮助FJ求出，在他恰当选择传送门的终点y的情况下，能够达到的所有di的和的最小值。在所有牛粪的运输中，终点位置y是相同的。

输入描述:

输入的第一行包含N。在下面的N行中，第i行包含ai和bi，每个整数都在-108...108之间。这些数值不一定各不相同。

输出描述:

输出一个数，为能够达到的di的和的最小值。注意这个数字可能超过标准的32位整数型能够表示的范围，所以你可能需要使用更大的数据类型，例如C/C++中的“long long”。同样你可能需要考虑答案是否一定是一个整数……

示例1

输入
3
-5 -7
-3 10
-2 7
输出
10
说明
在这个样例中，通过设置y=8，FJ可以实现d1=2，d2=5，d3=3。注意y取区间[7,10]中的任意值都能够得到最优解。

解答


首先问题的本质就是求如果当这个传送门的端点位于y的时候，最小的求出总代价，我们设为函数f(y)。

因为这个f(y)是一个具有分段线性的结构函数，我们就在求f(y)的时候遍历y，就可以了。每次当我们处理到两段函数的交界处时，我们就算出两个函数的斜率，算出其中的最小值。

因为有n个点，那么复杂度就是O(n)，但是一开始我们的各个点的顺序不定，那么我们需要花O(nlogn)的时间来进行排序，然后在用O(n)的时间遍历计算f(y)。

以上的算法比较的简单，但是我们需要用数学计算出每一个交接点的位置就是y的值，以及斜率多少和在每一个交接点的变化。

其中，表示只用于传送门的代价（第一部分表示直接移动，第二个部分表示如果使用传送门），每一个函数都是一个简单的函数，我们可以推导出以下的玩意：


对于交接点，每一个函数对最终的答案都是有贡献的，例如如果，那么就说明中没有交接点，那么答案就是讲向上平移。

对于图片中另外一种情况，如果并且，那么就说明有三个交接点，那么这个贡献的计算就是：当y=0时，的斜率-1，在y=b时+2，在y=2b时-1。

可以选择用map映射存储f(y)函数在各个交接点出的斜率的变化，然后再按照y的顺序遍历就可以得到答案了。 

# include <cstdio> # include <cstring> # include <algorithm> # include <ctype.h> # include <iostream> # include <cmath> # include <map> # define LL long long # define ms(a,b) memset(a,b,sizeof(a)) # define ri (register int) # define inf (0x7f7f7f7f) # define pb push_back # define fi first # define se second # define pii pair<int,int> using namespace std; inline int gi(){ int w=0,x=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return w?-x:x;
} int n; map<int,int>mp;
LL x=0,y=-inf,s=0; int main(){
    n=gi(); for (int i=1;i<=n;i++){ int a=gi(),b=gi();
        x+=abs(a-b); if (abs(a)>abs(a-b)) continue;
        mp[b]+=2; if ((a<b&&a<0)||(a>=b&&a>=0)) mp[0]--,mp[2*b]--; if ((a<b&&a>=0)||(a>=b&&a<0)) mp[2*b-2*a]--,mp[2*a]--;
    }
    LL ans=x; map<int,int>::iterator it; for (it=mp.begin();it!=mp.end();it++){ int ny=it->fi,tmp=it->se;
        x+=s*(ny-y); y=ny; s+=tmp;
        ans=min(ans,x);
    } printf("%lld\n",ans); return 0;
}


来源：Chhokmah