AT_abc393_d 题解

getchar_unlocked · 2025-02-17 21:33:49 · 题解

题目传送门

思路

首先将所有 1 的下标统计在序列 A 中，记为 A_0,A_1,\dots,A_{M-1}。为了最小化操作次数，应该将所有的数都移到最中间的 1 的位置上，即 A_{\lfloor\frac{M}{2}\rfloor}。

然后统计所有 1 移到中间所需交换次数，得到序列 B，则 B_i\gets A_{\lfloor\frac{M}{2}\rfloor}-\lfloor\frac{M}{2}\rfloor+i。

最后统计次数总和，即 \sum\lvert A_i-B_i\rvert。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=5e5+10;
char s[N];
int a[N],b[N];
signed main(){
    int n=read();
    scanf("%s",s);
    int m=0;
    for(int i=0;i<n;++i)
        if(s[i]=='1')
            a[m++]=i;
    for(int i=0;i<m;++i)
        b[i]=a[m/2]-m/2+i;
    int ans=0;
    for(int i=0;i<m;++i)
        ans+=(int)abs(a[i]-b[i]);
    printf("%lld\n",ans);
    return 0;
}