题目链接
\(Solution\)
先将所有棋子移动到最近的目标点上
我们设两个变量\(ans1,ans2\)表示到目前为止这个点上可以移动棋子的数目,然后\(f[i][j]\)表示\((i,j)\)上有多少个棋子,\(ans\)为答案
如果为正表示从左边移到右边
如果为负表示从右边移到左边
我们考虑怎么维护这个东西
我们考虑一下两种大情况：
这个位置上原本有值
那么我们只要将\(ans+(f[i][j]-1)\)即可这个位置本来没有值
我们考虑三种情况，我们以一行为例，其余的一行同理- \(ans1\)大于0,那么我们只需要将\(ans1--\)
- \(ans1<0\)&&\(ans2>0\) 我们将\(ans2--,ans+1\)表示从下面移上来(但是对于第一行的时候要注意一个事，下面会讲)
- 其余情况 \(ans1--\),表示从右边要借一个过来。
上面留了一个坑,对于第一行的时候后，在下面一行往上移的时候我们还要判断下面一行的情况。如果下面一行\(ans2==1,f[i][2]==0\)那么就不能移，因为要留着自己用
然后处理完之后会得到这一行的\(ans1\)和\(ans2\)于是我们在判断一下\(ans1\)和\(ans2\)是否为一正一负.
如果是则把绝对值小的那个移到另一行去,答案加上这个绝对值。
每次弄完之后,答案加上\(abs(ans1)+abs(ans)\)表示往后面移这些硬币
\(Code\)
#include<bits/stdc++.h>
#define int long long
#define rg register
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
const int N=1e6+10;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return f*x;
}
int X[N],Y[N],n,ans,flag1,flag2,ans1,ans2;
int f[N][3];
void solve(int x,int y){
int nowx=x,nowy=y;
if(x<=n&&x>=1&&y<=2&&y>=1) {f[x][y]++;return ;}
if(x>n) x=n;
if(x<1) x=1;
if(y>2) y=2;
if(y<1) y=1;
f[x][y]++,ans+=abs(nowx-x)+abs(nowy-y);
}
main(){
n=read();
for(int i=1;i<=2*n;i++)
X[i]=read(),Y[i]=read(),solve(X[i],Y[i]);
for(int i=1;i<=n;i++){
if(f[i][1]>1) ans1+=f[i][1]-1;
if(f[i][2]>1) ans2+=f[i][2]-1;
if(f[i][1]==0){
if(ans1>0) ans1--;
else if(ans2>0&&(ans2>1||(ans2==1&&f[i][2]))) ans2--,ans+=1;
else ans1--;
}
if(f[i][2]==0){
if(ans2>0) ans2--;
else if(ans1>0) ans1--,ans+=1;
else ans2--;
}
if(ans1<0&&ans2>0) {
if(abs(ans1)<abs(ans2))
ans2=ans2+ans1,ans+=abs(ans1),ans1=0;
else ans1=ans2+ans1,ans+=abs(ans2),ans2=0;
}
if(ans2<0&&ans1>0) {
if(abs(ans1)<abs(ans2))
ans2=ans2+ans1,ans+=abs(ans1),ans1=0;
else ans1=ans2+ans1,ans+=abs(ans2),ans2=0;
}
ans+=abs(ans1)+abs(ans2);
}
cout<<ans;
return 0;
}