Codeforces 1294E Obtain a Permutation(思维)

传送门

题意:

给出一个n*m的矩阵
两种操作:
1,可以把矩阵中的任一个数更改成任意值
2,把矩阵中的某一列整体上移一个单位
例如:
Codeforces 1294E Obtain a Permutation(思维)
第一列进行了2操作一次

问最少进行多少次操作把原来的矩阵变成
Codeforces 1294E Obtain a Permutation(思维)

思路:

分析,每一列之间的操作都是独立的,因此一列一列考虑即可
对于每一列,为了得到最少的操作次数,先进行1操作或者是2操作都是一样的,因此我们考虑一列数在向上移动\(i\)次之后,会是什么样的,一部分数已经符合要求,一部分需要改变,因此要变成最终的矩阵,需要操作的次数为 \(i+\)需要改变的个数,\(i\)可取\(1-n\),因此找到对应的最小值就可以了

代码:

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
vector<int>p[maxn];
int a[maxn];
int main()
{
    int n,m,x;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        p[i].push_back(0);//使vector下标从1开始
        for (int j = 1; j <= m; j++) {
            scanf("%d", &x);
            p[i].push_back(x);
        }
    }
        int ans=0;
    for(int j=1;j<=m;j++){
        int mi=maxn;

        for(int i=0;i<n;i++)a[i]=0;

        for(int i=1;i<=n;i++){
            if(p[i][j]<=n*m&&(p[i][j]-j)%m==0){
                int k=(p[i][j]-j)/m+1;//这个数应该在第几行
                a[(i-k+n)%n]++;//(i-k+n)%n为需要移动到第k行需要的操作次数,i可能大于或者小于k,+n取模即可,那么a[(i-k+n)%n]为移动(i-k+n)%n次之后符合最终矩阵的数的个数
            }
        }
        for(int i=0;i<n;i++) mi=min(mi,i+n-a[i]);//i为移动的次,a[i]为移动i次之后符合最终矩阵的数的个数,那么n-a[i]就是不符合
        ans+=mi;
    }
    printf("%d\n",ans);

    return 0;
}
上一篇:Python中置换的递归实现


下一篇:Java中的递归置换产生错误的结果