Codeforces Round #615 (Div. 3) E. Obtain a Permutation

E. Obtain a Permutation

原题链接：https://codeforces.com/contest/1294/problem/E

题目大意：

给一个无序矩阵，可以进行两个操作：

　　1.改变任何元素的大小；

　　2.将任何一列中的元素向上提一位，也就是$a_{1, j}:=a_{2, j}, a_{2, j}:=a_{3, j}, dots, a_{n, j}:=a_{1, j}$

使得最后的矩阵变为有序的序列，即$left.a_{1,1}=1, a_{1,2}=2, ldots, a_{1, m}=m, a_{2,1}=m+1, a_{2,2}=m+2, ldots, a_{n, m}=(i-1) cdot m+j ight)$

求最少的操作次数。

解题思路：

可知，每一列都是独立操作，所以可以计算每一列的最少操作数，首先开一个数组记录vis，以该列的第i行为起点所需进行的操作数。首先初始化为n+i(i从0开始)。然后遍历该列每一行算出如果这一行的数字属于该列，那么是以谁为起点才能使这个位置是它。计算得出答案为第a行，则vis[a]-1，然后计算到到最后一行，最后取最小值。在计算出每列最小值相加可得出最后答案。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+7;
vector<int>arr[N];
int vis[N];
int MAX,MIN;
int main(){
    int n,m,a,ans,idx;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        arr[i].push_back(0);
        for(int j=1;j<=m;j++){
            cin>>a;
            arr[i].push_back(a);
        }
    }
    ans=0;
    for(int j=1;j<=m;j++){
        for(int i=0;i<n;i++){
            vis[i]=n+i;
        }
        for(int i=1;i<=n;i++){
            if(arr[i][j]<=(j+m*(n-1))&&(arr[i][j]%m==j||(j==m&&arr[i][j]%m==0))){
                idx=i-arr[i][j]/m-1;
                if(j==m){
                    idx++;
                }
                idx=(idx+n)%n;
                vis[idx]--;
            }
        }
        MIN=1e9+7;
        for(int i=0;i<n;i++){
            MIN=min(MIN,vis[i]);
        }
        ans+=MIN;
    }
    cout<<ans<<endl;
    return 0;
}