「JOI 2019 Final」硬币收藏

题目链接

戳我

\(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;

}

巴特西

「JOI 2019 Final」硬币收藏

题目链接

\(Solution\)

\(Code\)

最新文章

热门文章

巴特西

「JOI 2019 Final」 硬币收藏

题目链接

\(Solution\)

\(Code\)

最新文章

热门文章

「JOI 2019 Final」硬币收藏