Codeforces 1294E - Obtain a Permutation

题目大意：

给定一个n*m的矩阵

可以更改任意一个位置的值

也可以选择一整列全部往上移动一位，最上方的数移动到最下方

问最少操作多少次可以把这个矩阵移动成

1 2 3 ... m

m+1 m+2 m+3 ... 2m

...

(n-1)m+1 (n-1)m+2 (n-1)m+3 ... nm

解题思路：

如果一个数大于n*m，或者这个数不属于这一列（(d-1)%m!=j）
那么这个数只能进行改变值的操作
存完后以列为单位分开求答案
用cnt[i]记录如果这一列移动k次的话，有多少数的值不需要进行更改
比如一列有10个元素，在向上移动5次后共有7个值回到了应该在的位置，那么此时n=10,cnt[5]=7
总共的操作次数为5+10-7=8次
由i+n-cnt[i]计算得来
所以在每次处理完cnt后遍历0到n-1求最优解，累加得出答案即可
在处理时，(v[j][i]-1)/m求出v[j][i]这个数原本应该在第几行
那么它的移动次数便是(i-d+n)%n
或者分开讨论
i>=d -> i-d
i<d -> i+n-d

#include<bits/stdc++.h>

using namespace std;

vector<int> v[];

int cnt[];

void solve(){

    int n,m,i,j,d,ans=,ansd;

    cin>>n>>m;

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

        for(j=;j<m;j++){

            cin>>d;

            if((d-)%m!=j||d>n*m)

                d=;//标记必须进行更改值

            v[j].emplace_back(d);

        }

    for(j=;j<m;j++){

        memset(cnt,,n*sizeof(int));

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

            if(v[j][i]){

                d=(v[j][i]-)/m;

                cnt[(i+n-d)%n]++;//计算如果要移动到应该在的位置需要移动几步

            }

        ansd=0x3f3f3f3f;

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

            ansd=min(ansd,i+n-cnt[i]);//寻找最优解

        ans+=ansd;

    }

    cout<<ans<<'\n';

}

int main(){

    ios::sync_with_stdio();

    cin.tie();cout.tie();

    solve();

    return ;

}

巴特西

Codeforces 1294E - Obtain a Permutation

最新文章

热门文章