P5971

Yashajin_Ai · 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;
}