Swap to Gather 题解

简易题意

给一个长度为 n 的 01 字符串，可以把相邻两个字符互换，求让所有的 1 相邻的最少步数。

思路

设

L

为最后互换完后所有的 1 相邻的左端点，设

C

为让所有的 1 相邻的最少步数。

易发现

C

关于

L

的函数是一个开口向上的单峰函数。则

\min C

为这个单峰函数的顶点，所以考虑三分。

又

2\leq\ N\leq\ 5\times\ 10^5

则可以通过

n\log n

级别的算法。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int a[N],num,ans=1e18,b[N],n;
int sum=0;
int f(int i){
	sum=0;
	for(int j=1;j<=num;j++) sum+=abs(b[j]-i-j+1);
	return sum;
}
int mid,mmid;
int sanfen(int l,int r){ 
 	int cnt=0;
    while(l<=r){   
     	cnt++;
    	if(cnt>1000) break;//保证精度
        mid = (l+r)/2;  
        mmid = (mid+r)/2;  
        if( f(mid) < f(mmid) )  r = mmid; 
        else  l = mid; 
    }  
	return min(min(f(mid),f(mmid)),min(f(l),f(r)));
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		char c;
		cin>>c;
		a[i]=c-'0';
		if(a[i]){
			num++;
			b[num]=i;
		}
	}
	cout<<sanfen(-100,n);
}

AT_abc393_d [ABC393D] Swap to Gather 题解

文章操作

Swap to Gather 题解

简易题意

思路

相关推荐

评论

AT_abc393_d [ABC393D] Swap to Gather 题解