U - Obtain a Permutation CodeForces

题解：

注意每一列与每一列之间互不影响，所以贪心地求出没一列的最小操作值，然后累加起来。

怎么求没一列的最小值呢？维护一个数组same表示其中same[i]=j表示将该序列向上翻滚i次有j个元素归位，那么会有n-j个没有归位，所以我们要修改他们，一共修改n-j次，所以总计n-j+i次。

所以每一列的答案为min(n-same[i]+i)；关于same的求法。首先每一列的元素的取值范围是j<=arr[i][j]<=n*m，并且arr[i][j]%m==j%m，即每一列的元素值对m取值应该相等。只有这样才是该列的元素。

对于那些不满足条件的不用考虑。因为无论翻转多少次,都无法使其归位。对于满足条件的，假设当前位置为j，然后其目标位置是pos.那么答案为(j-pos+n)%n即为翻转的次数。pos的取值:(arr[i][j]-j)/m+1;

所以same[(j-pos+n)%n]++;

code:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=2E5+;

vector<ll >ve[N];

ll same[N];//元素i向上移动same[j]个可以恢复

int main()

{

    ll n,m;

    cin>>n>>m;

    ll c=n*m;

    ll y;

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

        cin>>y;

        if(i%m==){

            ve[m].push_back(y);

        }

        else ve[i%m].push_back(y);

    }

    ll sum=;

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

        ll c=ve[i].size();

        for(ll j=;j<c;j++){

            if(ve[i][j]<i||ve[i][j]>n*m) continue ;

            if(ve[i][j]%m==i%m){

                ll pos=(ve[i][j]-i)/m+;

                ll k=(j+-pos+n)%n;

                same[k]++;            }

        }

        ll cnt=n;

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

            cnt=min(cnt,j+n-same[j]);

            same[j]=;

        }

        sum+=cnt;

    }

    cout<<sum<<endl;

    return ;

}

巴特西

U - Obtain a Permutation CodeForces - 1294E 思维

最新文章

热门文章