A New Beginning

题解

~~吐槽一下官方题解，当谜语人吗？~~

~~蒟蒻的做法是从诸位的代码中学习来的，大部分人的代码都好像呀，由于没找到一篇题解，所以就自己从代码中臆想了一下方法~~

我们很容易发现，对于对于点 $i$ ，路径上最优的一个匹配点一定有一个是在点 $i$ 所在的对角线 $x+y=x_{i}+y_{i}$ 上的。

假设我们在点 $(a, b) (a + b < x + y)$ ，对于点 $(x, y)$ ，我们现在的代价为 $m a x (∣ x - a ∣, ∣ y - b ∣)$ 。

当 $a < x, b < y$ 时，无论怎么走都不会变得更劣。

当 $a < x, b > y$ 时，由于 $x - a > b - y$ ，所以只有当我向下走的时候会变得更优，而向右走在到达对角线之前 $b - y$ 即使增大，也一直是小于 $x - a$ 的，不会变得更劣。

当 $a > x, b < y$ 时同理。

而当我们的 $a + b > x + y$ 时，也就是我们已经走过了对角线，

我们只能向右或向下走，但很明显，我们怎么也走不到代价更小的地方了。

所以可以发现，我们在对角线上时肯定是代价最小的。

由于我们每走一步只会让 $x + y$ 的和增加 $1$ ，所以我们的路径与 $x+y=x_{i}+y_{i}$ 肯定是有交点的。

但我们又该去怎么求总代价最小的路径呢？

首先是很容易考虑到 $d p$ 的，我们先将 $x_{i},y_{i})$ 按照 $x_{i}+y_{i}$ 的大小排序，设 $dp_{i}$ 表示在 $x = i$ 的点的最小代价。

走到 $x_{k},y_{k})$ 对应的对角线时，有转移
$dp_{i}=\min_{|j-i|\leqslant(x_{k}+y_{k}-x_{k-1}-y_{k-1})}(dp_{j}+|x_{k}-i|)$
很明显，直接这样转移的时候是 $O\left(10^9n\right)$ 的，不可能过得了。

我们可以寻找一下它转移的性质。

首先最优值肯定可以出现在一个已出现点对应的某个点(即它会在层与层之间向右或向下走到的点)上的。

我们可以先将新加入的点分成 $3$ 类，太左边以至于走不到，太右边以至于走不到，走得到。

这里用颜色区别开了。

我们假设 $S$ 的左边还有一些点，但它们没有 $S$ 优秀。

如果我接下来加入的点是在中央区域，这只会导致左边的相对差距增大，增大的值就是它们之间的相对距离。

但由于新加入的点可以由原来的最优点走到，原来的最优点又增大了，所以新点的值就是最优的了。它们之间的差距就是它们的相对距离。

如果加入的新点在蓝色区域，那么在新点左边与右边的点的 $d p$ 值都会增大。都是离新点越远增大的越多，增大的都是它们间的相对距离。

此时对于右边的点，就会产生变动了，如果最优点与次优点之间的差距只有它们之间的相对距离，那么此时的最优点就变成原来的次优点了。原来的最优点无论如何都不会在另一个新最优点出现之前变得比它更优。

如过新加入的点在红色区域呢?很显然，这只会继续让它们的相对差距增加。

对于在 $S$ 右边的点同理。

于是，我们想到可以维护两个优先队列。

一个表示左边部分的最优选择，其中最优点是最队列中最靠右的点。另一个表示右边的最优选择。

由于在这个对角线上，从左到右 $x$ 是递增的，从右到左 $y$ 是递增的，一个就按 $x$ 排序，一个按 $y$ 排序。

优先队列中往后的点与前面的点的差距与前面的点数有关，当这个点前面没有点时，它就是最优的了。

加入点时有如下三种情况。

如果加入的点在红色区域就往两个队列中各加入一个点，最优值没有变化。
如果加入的点在蓝色区域就找到 $x$ 对应队列的最优点，向里面加入两个新点，并将原来的最优点删除，最优值增加原来最优点与新点的差距。

如果原来的最优点有两个就说明它与后面的还有差距，它本身还是最优的，否则它就与下一个是相同的没用了。

但很明显，我们发现原来的最优点现在对于 $y$ 的那个序列还是有影响的，它会变成 $y$ 序列中的最优点，并加大 $y$ 间的相对差距。

所以我们还要填一个步骤。

并将这个最优点加入 $y$ 的队列中。
如果原来加入的点在红色区域，由于 $x$ 轴与 $y$ 轴是等价的，翻一翻也没问题，所以它们的操作应该也是相似的，只是对 $y$ 序列进行 $x$ 的操作罢了。

这样的时间复杂度是 $O\left(nlog\,n\right)$ 。

源码

其实代码挺简单的。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 800005
#define lowbit(x) (x&-x)
#define reg register
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL;
const int INF=0x3f3f3f3f;
const int mo=1e9+7;
const int iv2=5e8+4;
const int lim=1000000;
const int jzm=2333;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
typedef pair<int,int> pii;
const double PI=acos(-1.0);
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y){return x+y<mo?x+y:x+y-mo;}
int n,sum;LL ans;pii a[MAXN],b[MAXN];
bool cmp(pii x,pii y){return x.fir+x.sec<y.fir+y.sec;}
priority_queue<pii>qx,qy; 
signed main(){read(n);for(int i=1;i<=n;i++)read(a[i].fir),read(a[i].sec);sort(a+1,a+n+1,cmp);for(reg int i=1;i<=n;i++)b[i]=mkpr(a[i].sec,a[i].fir);qx.push(a[1]);qy.push(b[1]);for(reg int i=2;i<=n;i++){if(qx.top().fir>a[i].fir){pii t=qx.top();int dif=t.fir-a[i].fir;ans+=1ll*dif;qx.pop();qy.push(mkpr(a[i].sec-dif,a[i].fir+dif));qx.push(a[i]);qx.push(a[i]);}else if(qy.top().fir>b[i].fir){pii t=qy.top();int dif=t.fir-b[i].fir;ans+=1ll*dif;qy.pop();qx.push(mkpr(b[i].sec-dif,b[i].fir+dif));qy.push(b[i]);qy.push(b[i]);}else qx.push(a[i]),qy.push(b[i]);}printf("%lld\n",ans);return 0;
}