题解：AT_abc393_d [ABC393D] Swap to Gather

· · 题解

简单题。

找到最中间的那个然后挪过去计算长度就行。

证明不知道的话翻初一数学书。

/*
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[500010],sum[500010],Sum,cnt,cnt1,ans=10000000000000000;

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        char tmp;
        cin>>tmp;
        a[i]=(int)(tmp-'0');
        sum[i]=sum[i-1]+(int)(a[i]==0),cnt1+=(int)(a[i]==1);
    }
    for(int i=1;i<=n;i++){
        if(a[i])
            Sum+=sum[i];
    }
    int qwq=0;
    for(int i=1;i<=n;i++){
        int tmp=0;
        if(a[i]==1)
            qwq+=sum[i],cnt++;
        tmp=cnt*sum[i]-qwq+Sum-qwq-(cnt1-cnt)*sum[i];
        ans=min(ans,tmp);
    }
    cout<<ans;
}