题意描述

JOI 先生的收藏室里有一张巨大的桌子，上面有许多稀有的硬币。为了清理桌子，他要重新摆放硬币。

桌面可视为 $(2\times 10^9+1)\times (2\times 10^9+1)$ 的网格。JOI 先生有 $2N$ 枚硬币。初始时，第 $i$ 枚 $(1\le i\le 2N)$ 硬币被放在坐标为 $(X_i,Y_i)$ 的格子里。

JOI 先生的目标是在每个满足 $1\le x \le N,1\le y\le 2$ 的格子 $(x,y)$ 上恰好放一枚硬币。为了不损坏硬币，他能做的唯一一个操作是钦定一枚硬币然后将其移动到相邻的一个格子中（我们说两个格子相邻，当且仅当这两个格子有公共边）。

在移动硬币的过程中，允许两个硬币处在同一个格子中。JOI 先生希望通过尽量少的操作次数完成目标。

现在给出硬币的数量和初始时所在的位置，编写一个程序，计算完成 JOI 先生目标所需的最少操作次数。

输入格式

第一行一个整数 $N$。

接下来 $2N$ 行，第 $i$ 行为两个整数 $X_i$ 和 $Y_i$。

输出格式

输出一行一个整数，表示完成目标所需的最少操作次数。

Input & Output ‘s examples

Input ‘s eg 1

3
0 0
0 4
4 0
2 1
2 5
-1 1

Output ‘s eg 1

15

Input ‘s eg 2

4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1

Output ‘s eg 2

9

Input ‘s eg 3

5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3

Output ‘s eg 3

8000000029

数据范围和约定

对于 $100\%$ 的数据，$1 \leq N \leq 10^5,-10^9\le X_i,Y_i\le 10^9$。

分析

先考虑矩形范围只有一行时候怎么做。

显然，只有一行的时候就把所有的硬币以最短路径移动到该行中，然后扫一遍就行了。

之后考虑两行的时候有什么不同？

两行时显然我们还要把每个硬币以最短路径移动到矩形中，移动之后可能会出现某些格子里没有硬币，而某些格子里硬币很多的状况。

开一个桶 $cnt[i][1/2]$ 表示第 $1/2$ 行的第 $i$ 列还需要多少硬币，之后从前往后扫一遍。

若出现两行中同一列的 $cnt$ 一正一副，则移动至其中一行为 $0$ ，否则将多余的硬币分给下一列即可。

时间复杂度为 $O(n)$

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 1000000 + 5;
const int HA = 998244353;

ll n , x[M] , y[M];
ll cnt[M][3];

ll res;

int main() {
    #ifdef LOCAL
        freopen("c.in" , "r" , stdin);
        freopen("c.out" , "w" , stdout);
    #endif
    read(n);
    rep(i , 1 , 2 * n) {
        read(x[i]) , read(y[i]);
        if(x[i] < 1) res += (ll)abs(1 - x[i]) , x[i] = 1;
        if(x[i] > n) res += (ll)abs(x[i] - n) , x[i] = n;
        if(y[i] < 1) res += (ll)abs(1 - y[i]) , y[i] = 1;
        if(y[i] > 2) res += (ll)abs(y[i] - 2) , y[i] = 2;
        cnt[x[i]][y[i]] ++;
    }
    ll l1 = 0 , l2 = 0;
    rep(i , 1 , n) {
        l1 += cnt[i][1] - 1 , l2 += cnt[i][2] - 1;
        while(l1 < 0 && l2 > 0) ++ l1 , -- l2 , ++ res;
        while(l2 < 0 && l1 > 0) ++ l2 , -- l1 , ++ res;
        res += abs(l1) + abs(l2);
    }
    printf("%lld\n" , res);

    return 0;
}

THE END