ABC393D题解

Lovely_yhb · 2025-02-16 08:20:40 · 题解

题意

给定一个长度为 n 的 01 串，每次可以交换两个相邻的位置，问至少多少次交换可以让所有的 1 都在一起。

思路

容易发现最中间的 1 不动，把两边的向中间靠是最优的。

如何确定最中间的？考虑 1 的个数 cnt，如果是奇数，那肯定就是第 \frac{cnt+1}{2} 个 1。

对于每个为 1 的位置计算移动的步数。设第 i 个 1 的位置为 a_i，mid=\frac{cnt+1}{2}，第 i 个为 1 的位置需要移动的步数是 (|a_{mid}-a_i|-1)-(|mid-i|-1)。

这是因为如果从 i 位置移动到与 mid 位置相邻，需要 |a_{mid}-a_i|-1 步，但由于中间隔了 |mid-i|-1 个 1，所以这些步不用动。

如果 cnt 是偶数，中间的可能是 \frac{cnt}{2} 或 \frac{cnt}{2}+1。那就令 mid=\frac{cnt}{2} 和 mid=\frac{cnt}{2}+1 各跑一遍，两次答案取 \min 即可。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n,cnt=0,cur=0,a[N],ans=0;
char s[N];
signed main(){
    cin>>n;
    cin>>s+1;
    for(int i=1;i<=n;i++)  if(s[i]=='1') a[++cnt]=i;
    if(cnt&1){
        int mid=(cnt+1)/2,val=a[(cnt+1)/2];
        for(int i=1;i<=cnt;i++) ans+=max(0ll,abs(val-a[i])-abs(mid-i));
        cout<<ans;
    }else{
        int mid1=cnt/2,mid2=cnt/2+1;
        int t1=0,t2=0;
        for(int i=1;i<=cnt;i++) t1+=max(0ll,abs(a[mid1]-a[i])-abs(mid1-i));
        for(int i=1;i<=cnt;i++) t2+=max(0ll,abs(a[mid2]-a[i])-abs(mid2-i));
        cout<<min(t1,t2);
    }
    return 0;
}