USACO 2018 February Contest，Silver Problem 3. Teleportation
写在前面 ——3.19 考试总结
这次考试各路神仙失踪。有的人因为循环变量，导致两道题与 AC 背道而驰；有的人因为打表忘删，一个小时思考的成果付之东流……各种各样的错误都有，而我，幸好手动对拍，保住了前两题的分，在排名上相对靠前。有的是庆幸，有的是喜悦，也有心慌。时间恍如细沙，握得越紧，流逝地便也越快。再流逝的时间里，能做到的，就是把能抓住的分抓紧，而不是在前行的道路上泪流满面，步步回头。静下心来，再仔细看看。
Description
（题目太长，讲个大概）有 N 样货物，需要从 ai 运到 bi ，步行路程 di = | ai - bi | 。现有一个传送通道，从 0 进入可以直接到达 y 。现由你确定一个 y ，使得步行路程最短。输出最小的步行路程。
Input
输入的第一行包含N。在下面的N行中，第 i 行包含 ai 和 bi，每个整数都在 −10^8…10^8 之间。这些数值不一定各不相同。
Output
输出一个数，为能够达到的 di 的和的最小值。注意这个数字可能超过标准的32位整数型能够表示的范围，所以你可能需要使用更大的数据类型，例如C/C++中的“long long”。同样你可能需要考虑答案是否一定是一个整数……
Sample Input
3
-5 -7
-3 10
-2 7
Sample Output
10
首先，对于" 同样你可能需要考虑答案是否一定是一个整数……"，显而易见是没有必要的，因为 a[i] 和 b[i] 都为整数，y 一定可以取到整数，所以答案一定为一个整数。
同样思考：什么时候需要利用传送门？
显然，当 abs(a[i]-0)+abs(b[i]-y)<abs(a-b) 时，才会选择传送门。
由于并没有给出 y 值，所以当 abs(a[i]-0)<abs(a-b) 时，就判断可能使用传送门。
对于每一个 a[i] 和 b[i] ，有以下几种情况（a[i] 和 b[i] 以 a 和 b 来代替）：
1. 当 b<=a<0 时，y = 2*b-2*a ~ 2*b+2*a 能够对答案产生影响。
2. 当 a<0，a<b 时，y = 0 ~ 2b 能够对答案产生影响。
3. 当 a>=0，a>=b 时，y = 0 ~ 2b 能够对答案产生影响。
4. 当 b>a>=0 时，y = 2*b-2*a ~ 2*b+2*a 能够对答案产生影响。
（*请不要以数学思维衡量一下的图）
第 4 种情况的函数图像（第 1 种情况与之类似）：
第 3 种情况的函数图像（第 2 中情况与之类似）：
斜率公式为：
由此，可以推出斜率为 -1，+1。
所以，在左右两个转折点处（即为 y 能影响的范围边界）--，在中间处（即为 b）+2。可以发现：这样，是从左边界到中间点的差分前缀和为 -1 ，从中间点到右边界的差分前缀和为 +1。符合了所推的斜率。
#include<bits/stdc++.h>
using namespace std;
int N;
long long anss=0,ans=0,tot,la;
struct kk{ int a; int b; } E[100010]={};
bool mycmp(kk x,kk y){ return x.b<y.b; }
map<long long,int> vis;
int main(){
freopen("teleport.in","r",stdin);
freopen("teleport.out","w",stdout);
scanf("%d",&N);
for(int i=1;i<=N;i++){
int a,b;
scanf("%d%d",&a,&b); ans+=abs(a-b);
if(abs(0-a)>=abs(a-b)) continue;
vis[b]+=2;
if(a<0){
if(b<=a) vis[2*a]--,vis[2*b-2*a]--;
else vis[0]--,vis[2*b]--;
}else{
if(a<=b) vis[2*a]--,vis[2*b-2*a]--;
else vis[0]--,vis[2*b]--;
}//差分
}
anss=ans;
for(map<long long,int>::iterator i=vis.begin();i!=vis.end();i++)//map从左到右遍历
anss+=tot*(i->first-la),la=i->first,tot+=i->second,ans=min(ans,anss);//依据斜率进行相应加减
printf("%lld\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}