硬币收藏

NC53191. 硬币收藏

描述

译自 JOI 2019 Final T4「コイン集め / Coin Collecting」

JOI先生的收藏室里有一张巨大的桌子，上面有许多稀有的硬币。为了清理桌子，他要重新摆放硬币。
桌面可视为 $(2 \times10^9+1) \times(2 \times10^9+1)$ 的网格。网格上往下数第i行（ $-10^9 \le i \le 10^9$ ），左往右数第j列（ $-10^9 \le j \le 10^9$ ）的格子坐标记为(i,j)。
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行为两个整数和。

输出描述

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

示例1

输入:

输出:

说明:

一种合法的移动方案是：
一号硬币： $(0,0) \rightarrow(1,0) \rightarrow(1,1) \rightarrow(1,2)$
二号硬币： $(0,4) \rightarrow(1,4) \rightarrow(1,3) \rightarrow(2,3) \rightarrow(3,3) \rightarrow(3,2)$
三号硬币： $(4,0) \rightarrow(4,1) \rightarrow(3,1)$
五号硬币： $(2,5) \rightarrow(2,4) \rightarrow(2,3) \rightarrow(2,2)$
六号硬币： $(-1,1) \rightarrow(0,1) \rightarrow(1,1)$
可以证明JOI先生不能用少于15次移动完成目标。

示例2

输入:

输出:

示例3

输入:

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

输出:

8000000029

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 242ms, 内存消耗: 1748K, 提交时间: 2020-05-13 17:54:21

#include <bits/stdc++.h>
using namespace std;
int b[1000005][3],n;
long long ans=0;
int main(){
    cin>>n;
    for(int x,y,i=1;i<=2*n;i++){
        cin>>x>>y;
        if(x<1){
            ans+=1-x;
            x=1;
        }
        if(x>n){
            ans+=x-n;
            x=n;
        }
        if(y<1){
            ans+=1-y;
            y=1;
        }
        if(y>2){
            ans+=y-2;
            y=2;
        }
        b[x][y]++;
    }
    for(int i=1,x=0,y=0;i<=n;i++){
        x+=b[i][1]-1;
        y+=b[i][2]-1;
        while(x<0&&y>0){
            x++;
            y--;
            ans++;
        }
        while(x>0&&y<0){
            x--;
            y++;
            ans++;
        }
        if(i<n)
        ans+=abs(x)+abs(y);
    }
    cout<<ans;
}

C++11(clang++ 3.9) 解法, 执行用时: 101ms, 内存消耗: 5228K, 提交时间: 2020-04-15 21:07:30

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,i,x,y,ans,a[500010][2];
int main(){
	scanf("%lld",&n);
	for(i=1;i<=n*2;i++){
		scanf("%lld%lld",&x,&y);
		if(x<1)ans+=1-x,x=1;
		if(y<1)ans+=1-y,y=1;
		if(x>n)ans+=x-n,x=n;
		if(y>2)ans+=y-2,y=2;
		a[x][y]++;
	}
	x=y=0;
	for(i=1;i<=n;i++){
		x+=a[i][1]-1;y+=a[i][2]-1;
		while(x<0&&y>0)x++,y--,ans++;
		while(x>0&&y<0)x--,y++,ans++;
		ans+=abs(x)+abs(y);
	}
	printf("%lld",ans);
}