纯洁的泪水在我心间汩汩涌动

· · 题解

一刚开始想加写的很复杂，其实并没有那么恶心。

感觉还是很困难的贪心。

考虑一个很显然的东西就是大坐标轴背景其实是虚假的，直接走到最近的范围内的点上然后做进一步的子问题显然是最优的。

可以考虑最后匹配过程上的形成形式，发现若任意点到其匹配的目标点，由于是曼哈顿距离，先走到范围内最近点再走到目标点是不劣的。

考虑一维问题怎么做，一个贪心是根据空的位置和多余位置的棋子按顺序一一匹配，考虑函数化的表达，滚前缀和，每次维护有多少个棋子必定要向左右移动将贡献平摊到每个 i \rightarrow i+ 1 或 i + 1 \rightarrow i 的间隙上。

回归二维，不考虑两行的跨越传递棋子，我们发现问题变成：

考虑跨越传递棋子。将其放在转化问题时就是消耗 1 的代价，使得 L \leftarrow L + 1,R \leftarrow R - 1 或 R \leftarrow R + 1,L \leftarrow L - 1。

不妨大胆猜测一个结论：每次若 L,R 一正一负时互相递补调整，最后求和就是最优策略。

考虑任意的 c_{x,y} \in [-1,2n]，我们发现每次递补调整时大多数情况都会让当前的 |L| + |R| 减少 2 - 1 = 1，只有当 L,R 为 -1,+1 且下次的 c 为 1,-1 才会造成当前的操作不劣。

并且我们发现由于保证 \sum = 2n，且 L,R 在最后的值代表了有 n + x 个棋子这样的含义，操作的目标导向为“尽量使两者值都为 0”，最后一定能保证 L = 0,R = 0，即分配两行棋子平均的定义。

我们可以发现该种操作的所有可能导致的后效性都是不劣的，并且所有的后续影响都是最优的，故可以默认为后效性其实是不存在的，这样最优子结构也可以被提出来，贪心的正确性也可以得到证明。我不知道这个表达是否准确，也许是自己的理解。

时间复杂度 O(n)。

/*
考虑对于极大坐标轴是假的，显然移动到最近的范围区域后重新分配是对的。
如果是一维的话很简单，显然必须对应填是最小的。
考虑加了一行，咋做
离线下来成一维序列，考虑 dp，设 dp_{i,l,r} 当走到 i 时表示上面前 l 个下面前 r 个的最小花费
然后咋搞，感觉就不平凡了。
先来看一下转移式
dp_{i,l,r} = min(dp_{i - 1,l - 1,r} + opt + dis(i,l) , dp_{i - 1,l,r - 1} + opt + dis(i,r))  
首先，一个点上有的就不动了。 
可以发现重叠的路径之间是可以 swap 的。
然后就有一个很显然的贪心了？ 
*/
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int Len = 1e5 + 5;
int n,m;
int sm[2],ct[Len][2];
#define ll long long
inline int Iabs(int x){if(x < 0) x = -x;return x;}
ll as = 0;
int sum[Len];
signed main()
{
    scanf("%lld",&n);
    for(int i = 1 ; i <= (n << 1) ; i ++)
    {
        int x,y;scanf("%lld %lld",&x,&y);
        if(x <= 0) as += Iabs(x - 1) , x = 1;
        if(x > n) as += Iabs(x - n) , x = n;
        if(y <= 0) as += Iabs(y - 1) , y = 1;
        if(y > 2) as += Iabs(y - 2) , y = 2;
        ct[x][y] ++;
        //printf("!%d %d\n",x,y);
        sm[y] ++;
    }
    //printf("%lld\n",as);
    int opt = 1;
    int L = 0 , R = 0;
    for(int i = 1 ; i <= n ; i ++)
    {
        L += ct[i][1] - 1 , R += ct[i][2] - 1;
        while(L > 0 && R < 0) L -- , R ++ , as ++;
        while(L < 0 && R > 0) R -- , L ++ , as ++;
        //printf("%d %d\n",L,R);
        as += Iabs(L) + Iabs(R);
    }
    printf("%lld\n",as);
    return 0;
}