14673 Coin Collecting

题意

现有2n个硬币,每个硬币在桌子上有自己的坐标(x,y),现在希望将它们全部移动到左下角为(1,1),右上角为(n,2)的矩形中,并且每个坐标仅有一枚硬币,求最小移动步数(移动是指上下左右为一次移动)

思路

不妨把这个题拆解成两部分,第一步是把所有硬币移动到矩形范围内(用最小步骤,可重叠),第二步将矩形内硬币重排成每个坐标仅有一枚硬币。
第一步:把每个硬币移动到矩形中离它最近的那个位置。不难发现,这个位置是唯一的,且容易求得(如果超出范围取max或min即可)
第二步:从左到右(右到左也行 ~上到下或者下到上不会~)扫一遍,如果当前列数目超了,就把硬币往右移动,如果不够,则把右边的向左移动(右侧的可以为负数,理解成向右侧借一个,由于总数确定,可以加回来的)。如果上下一多一少,则先内部调整一下再向右侧调整。因为是两行,可以直接搞出来。

正确性分析

这样得到的答案必为最优解,因为每步移动可以拆解成xy方向分别移动,而与移动的先后顺序无关(比如右1上1右1和右2上1答案相同),因此只要过程中不会折返,得到的就必为最优解。
显然,第一步和第二步内不可能发生折返的情况,在第一步时,找到的是最近的格子,意味着其他格子都比找到的格子远,因此去任何格子都不会折返(因为折返只会近)

代码

//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const double eps=1e-10;
int c[N][3];
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
#endif

    ll ans=0;
    int n;
    cin>>n;
    for(int i=1;i<=n*2;i++)
    {
        ll x,y;
        cin>>x>>y;
        if(y>2) ans+=y-2,y=2;
        if(y<1) ans+=1-y,y=1;
        if(x>n) ans+=x-n,x=n;
        if(x<1) ans+=1-x,x=1;
        c[x][y]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(c[i][1]>1&&c[i][2]<1){
            int p=min(c[i][1]-1,1-c[i][2]);
            c[i][1]-=p, c[i][2]+=p, ans+=p;
        }
        if(c[i][2]>1&&c[i][1]<1) {
            int p=min(c[i][2]-1,1-c[i][1]);
            c[i][2]-=p, c[i][1]+=p, ans+=p;
        }
        if(c[i][1]!=1)
        {
            int p=c[i][1]-1;
            ans+=abs(p);
            c[i+1][1]+=p;
            c[i][1]=1;
        }
        if(c[i][2]!=1)
        {
            int p=c[i][2]-1;
            ans+=abs(p);
            c[i+1][2]+=p;
            c[i][2]=1;
        }
    }
    cout<<ans;
    return 0;
}