自动搬运

查看原文

来自洛谷，原作者为

	Yashajin_Ai 夜叉神天衣--Yashajin_Ai

搬运于2025-08-24 22:16:06，当前版本为作者最后更新于2023-05-25 22:47:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

看到这道题最开始感觉十分像汉诺塔，但是会发现这个不需考虑大小的限制只要让每一个到达规定位置就可以了，那么其实就可以直接去考虑贪心的策略。

第一种贪心方法：分别计算出前 $cnta$ 个 $a_j$ 中不为 $1$ 的数有多少，再计算后 $cnta$ 个 $a_j$ 不为 $1$ 的数有多少，$b_j$ 记录反之，最后将所需步数与当前最小值比较取最小值,这个方法是三种数字一起考虑移动。

第二种贪心方法：只去处理 $b_j$ 为 $1$ 的情况，这些移动代价为 $1$，那如果碰到 $b_j$ 不为 $1$ 的话，代价便会多出 $1$，自然这是移动除 $1$ 之外的数.

第三种贪心方法：类似于第二种，是去处理 $a_j$，不为 $1$ 时代价为 $1$，为 $1$ 时代价会比不是 $1$ 时代价多 $1$，这种方法是照顾不是 $1$ 的数，使他们步数尽量少。

浅浅的证明一下这种贪心的可行性，贪心是一种求当前最优解的算法，这个题并没有博弈论那样考虑全局的条件在里面，没有任何大小限制的盘子，三种贪心，考虑了所有贪心的情况，所以一定能找到最小值。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000001;
int s[N],n,ans=INT_MAX,a[N],b[N],cnta,cntb,n_ex_t[N];
bool chk(int x){//第x位后会不会更优
    int tot=0;
    bool pd=0;
    for(int i=x+1;i<n_ex_t[x];i++){
        if(s[i]==1){
            tot++;
            pd=1;
        }
        else{
        	if(pd){
				tot--;
			}
		}
    }
    return tot<1;
}
void solve(int x){
    int as=0,c[N],tot=0,n_ex=-1,sum=0/*现在已经走了多少步了*/,k1=0,k2=0,k3=0,k4=0;;
    for(int i=n;i>=1;i--){
        if(s[i]==x){
            sum++;
            n_ex_t[i]=n_ex;
            n_ex=i;
        }
    }
    n_ex_t[0]=n_ex;
    bool pd=0;//是否已经出现了不合法
    int i=0;
    for(i=0;n_ex_t[i]!=-1;i=n_ex_t[i]){
        if(pd==0){
            if(chk(i)){
                for(int j=i+1;j<n_ex_t[i];j++)
                    if(s[j]!=1){
                        sum++;
                    }
                for(int j=i+1;j<n_ex_t[i];j++)
                    if(s[j]==1){
                        sum=sum+2;
                        c[++tot]=s[j];
                   	}
            	}
            else{
            	pd=1;
			}
        }
        if(pd==1){
            for(int j=i+1;j<n_ex_t[i];j++){
                c[++tot]=s[j];
                sum++;
            }
        }
        for(int j=i+1;j<n_ex_t[i];j++){
        	if(s[j]==1){
        		pd=1;
			}
		}
    }
    i++;
    cnta=0,cntb=0;
    for(int j=i;j<=n;j++){
    	a[++cnta]=s[j];
	}
    for(int j=tot;j>=1;j--){
    	b[++cntb]=c[j];
	}
    while(cnta>0&&a[cnta]==1){
    	cnta--;
	}
    while(cntb>0&&b[cntb]!=1){
    	cntb--;
	}
    for(int j=cnta;j>=1;j--){
        if(a[j]==1){
        	break;
		}
        k1++;
    }
    for(int j=cntb;j>=1;j--){
        if(b[j]!=1){
        	break;
		}
        k2++;
    }
    for(int j=1;j<=cnta;j++){
        if(a[j]==1){
        	break;
		}
        k3++;
    }
    for(int j=1;j<=cntb;j++){
        if(b[j]!=1){
        	break;
		}
        k4++;
    }
    ans=min(ans,sum+k1+k2+min(k1,k2)+2*(cnta-k1)+2*(cntb-k2));//贪一
    as=0;
    for(int j=1;j<=cntb;j++){
        if(b[j]==1){
        	as++;
		}
        else{
        	as=as+2;
		}
    }
    ans=min(ans,sum+as+cnta*2);//贪二
	as=0;
    for(int j=1;j<=cnta;j++){
        if(a[j]==1){
        	as=as+2;
		}
        else{
        	as++;
		}
    }
    ans=min(ans,sum+as+cntb*2);//贪三
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>s[i];
	}
    solve(2);
    solve(3);
    cout<<ans;
}