AT_abc393_d [ABC393D] Swap to Gather 题解

· · 题解

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 级别的算法。

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