思路

每一個硬幣最終都會走到 \(2 \times n\) 的矩形里面，所以不妨將它們先到其到矩形中最近的節點。

現在只需要在這個矩形中調整使每一個位置都有一個硬幣。貪心的，我們希望讓 \(x\) 更小的填的位置盡量靠前。

從前往后掃，記 \(a,b\) 分別表示 \(y = 1,y = 2\) 的多余的硬幣。當 \(a > 0,b < 0\) 時，需要將 \(a\) 分一些給 \(b\)；當 \(a < 0,b > 0\) 時，需要將 \(b\) 分一些給 \(a\)。因為我們在此時需要將 \(|a| + |b|\) 個硬幣移動到經過該點，加上貢獻即可。

Code

#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second
#define int long long

using namespace std;

typedef pair<int,int> pii;
const int N = 1e5 + 10;
const int inf = (int)(1e18) + 10;
int n,ans;
int num[N][5];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

signed main(){
    n = read();
    for (re int i = 1,x,y;i <= 2 * n;i++){
        x = read(),y = read();
        if (x < 1){ ans += (1 - x); x = 1; }
        else if (x > n){ ans += (x - n); x = n; }
        if (y <= 1){ ans += (1 - y); y = 1; }
        else{ ans += (y - 2); y = 2; }
        num[x][y]++;
    }
    for (re int i = 1,a = 0,b = 0;i <= n;i++){
        a += (num[i][1] - 1),b += (num[i][2] - 1);
        while (a > 0 && b < 0) a--,b++,ans++;
        while (a < 0 && b > 0) a++,b--,ans++;
        ans += (abs(a) + abs(b));
    } printf("%lld",ans);
    return 0;
}