E. Obtain a Permutation

题意：给定一个n*m的矩阵，你需要通过操作变成目标矩阵，每一次操作可以是修改一个数，可以是将一列循环上升一位，求最小的操作次数。

分析

其实这题只能算是一个暴力题，每一列其实是独立的，把每一列的最小操作次数求出来累加就是结果。而对于每一列，需要统计出每一个元素需要几次上升操作能够移动到正确位置上，用step[i] = c 表示，此列向上移动i次，可以有c个元素移动到正确位置上。当统计完一列之后复杂度是O(n),然后再进行n次循环进行ans = min(ans,i+n-step[i]) i:上升操作次数，n-step[i]改变次数，复杂度也是O(n)，加在一起还是O(n)
然后累加ans就可以了

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e6+10;

int N,M,res;
int arr[maxn],step[maxn];
int main(){
    cin>>N>>M;
    for(int i = 1;i<=N;i++){
        for(int j = 1;j<=M;j++){
            scanf("%d",&arr[i*M+j]);
        }
    }
    for(int j = 1;j<=M;j++){
        memset(step,0,sizeof(int)*N+10);//让初始化与N的大小有关
        int mi = 1e9;
        for(int i = 1;i<=N;i++){
            int cur = arr[i*M+j];
            if(cur>N*M || (cur-j)%M != 0) continue;
            int idx = (cur+M-1)/M;
            int mov = i>=idx? i-idx:i+N-idx;
            step[mov]++;
        }
        for(int k = 0;k<=N;k++){
            mi = min(mi,k + N -step[k]);
        }
        res += mi;
    }
    cout<<res<<endl;
    return 0;
}