E1. Send Boxes to Alice (Easy Version)

题解：

保存每个1的位置。然后记录1的总个数cnt，如果存在一个k使得这个k是每个集合的倍数，那么为了使操作次数最小，这个k应该是cnt的质因子。（因为都是每个集合的数目1，使每个集合的数目变为2需要的次数一定小于使每个集合数目变为4需要的次数）

枚举cnt的质因子x，即x个1构成一个新的集合。构成新集合的时候要是两边的1往中间凑（中位数）。剩下的就暴力。。。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF=1e18+;

const ll N=1E5+;

ll arr[N];

vector<ll >ve;

ll cal(ll x){

    ll sum=;

    ll x1=x/;

    for(ll i=;i<ve.size();i+=x){

        for(ll j=i;j<i+x1;j++){

            sum+=ve[i+x1]-ve[j];

        }

        for(ll j=i+x-;j>i+x1;j--){

            sum+=ve[j]-ve[i+x1];

        }

    }

    return sum;

}

void solve(){

    ll n;

    cin>>n;

    ll cnt=;

    for(ll i=;i<=n;i++){

        cin>>arr[i];

        if(arr[i]){

            cnt++;

            ve.push_back(i);

        }

    }

    if(cnt==||n==){

        cout<<-<<endl;

        return ;

    }

    ll m=sqrt(cnt);

    ll sum=INF;

    for(ll i=;i<=m;i++){

        if(cnt%i==){

            sum=min(sum,cal(i));

            while(cnt%i==) {

                cnt/=i;

            }

        }

    }

    if(cnt!=){

        sum=min(sum,cal(cnt));

    }

    cout<<sum<<endl;

    return ;

}

int main(){

    solve();

    return ;

}

巴特西

E1. Send Boxes to Alice (Easy Version)

最新文章

热门文章