E.Obtain a Permutation
You are given a rectangular matrix of size n×m consisting of integers from 1 to 2⋅105.
In one move, you can:
choose any element of the matrix and change its value to any integer between 1 and n⋅m, inclusive;
take any column and shift it one cell up cyclically (see the example of such cyclic shift below).
A cyclic shift is an operation such that you choose some j (1≤j≤m) and set a1,j:=a2,j,a2,j:=a3,j,…,an,j:=a1,j simultaneously.
Example of cyclic shift of the first column
You want to perform the minimum number of moves to make this matrix look like this:
In other words, the goal is to obtain the matrix, where a1,1=1,a1,2=2,…,a1,m=m,a2,1=m+1,a2,2=m+2,…,an,m=n⋅m (i.e. ai,j=(i−1)⋅m+j) with the minimum number of moves performed.
Input
The first line of the input contains two integers n and m (1≤n,m≤2⋅105,n⋅m≤2⋅105) — the size of the matrix.
The next n lines contain m integers each. The number at the line i and position j is ai,j (1≤ai,j≤2⋅105).
Output
Print one integer — the minimum number of moves required to obtain the matrix, where a1,1=1,a1,2=2,…,a1,m=m,a2,1=m+1,a2,2=m+2,…,an,m=n⋅m (ai,j=(i−1)m+j).
Examples
Input
3 3
3 2 1
1 2 3
4 5 6
Output
6
题意：
给一个n*m的矩阵
有两种操作:
1.把某一格的数任意修改成一个数
2.把某一列循环上移一步
现在要使得a[1][1]=1,a[1][2]=2....a[n][m]=n*m
问最少需要多少次操作
思路：
显然每一列都是独立的
对于每一列求出移动k次需要的最小操作次数c[k],然后ans+min(c[k])即可
做法:
对于每一列c[i]初始化为i+n,意思是移动i次之后n个数都要修改一次,总共i+n
然后遍历当前列的元素,如果a[i][j]%m==j说明这个元素在这一列有位置
令dif=i-a[i][j]/m,如果dif<0则dif+n,这是移动到应有位置所需的次数
然后c[dif]--,意思是移动dif次的话,最后需要修改的次数就减少1
遍历完之后ans+=min(c[k])即可
ps:
有个坑点是a[i][j]可能大于n*m,这种数只能进行修改操作,遍历的时候要跳过
code：
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,m;
cin>>n>>m;
vector<vector<int> >a(n,vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
a[i][j]--;
}
}
int ans=0;
for(int j=0;j<m;j++){
vector<int>c(n);
for(int i=0;i<n;i++){//移动i次之后最小的操作次数
c[i]=i+n;//初始为移动的i次加上全修改n次
}
int mi=n;//存当前列的最少操作次数
for(int i=0;i<n;i++){
if(a[i][j]>=n*m)continue;//有超出范围的数,只能修改,不continue会RE
if(a[i][j]%m==j){//如果a[i][j]属于这一列
int dif=i-a[i][j]/m;//求出移动次数
if(dif<0)dif+=n;
c[dif]--;//如果移动dif次,需要的操作-1
mi=min(mi,c[dif]);
}
}
ans+=mi;
}
cout<<ans<<endl;
return 0;
}