「JOI 2019 Final」 硬币收藏

题目链接

戳我

\(Solution\)

先将所有棋子移动到最近的目标点上

我们设两个变量\(ans1,ans2\)表示到目前为止这个点上可以移动棋子的数目,然后\(f[i][j]\)表示\(i,j\)上有多少个棋子,ans为答案

如果为正表示从左边移到右边

如果为负表示从右边移到左边

我们考虑怎么维护这个东西

我们考虑一下两种大情况：

1. 这个位置上原本有值
   那么我们只要将ans+(f[i][j]-1)即可
2. 这个位置本来没有值
   我们考虑三种情况，我们以一行为例，其余的一行同理
   • 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;
//  cout<<x<<" "<<y<<endl;
    f[x][y]++,ans+=abs(nowx-x)+abs(nowy-y);
    
}
main(){
//  file("coin");
    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」 硬币收藏

原文：https://www.cnblogs.com/hbxblog/p/11743395.html