ABC393D题解

题意

给定一个长度为

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

CPP

#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;
}

文章操作

题意

思路

AC Code

相关推荐

评论

ABC393D题解