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

glm233

发布于 2020-09-28 11:11:03

3170

发布于 2020-09-28 11:11:03

文章被收录于专栏：glm的全栈学习之路

E. Obtain a Permutation

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

题意：

给你一个 n * m 的矩阵，你执行两种操作：

① 把矩阵中任意一个元素改为任意一个数

② 把矩阵中任意一列整体往上挪一个单元格，如下图矩阵我们对第一列向上挪了一个单元格

现要求用最少的操作次数使矩阵内每一个元素 a[i][j] = (i - 1) * m + j

理智分析：第j排的目标是确定的：{j,j+m,j+2*m,.....,j+(n-1)*m}；

暴力模拟每一次移动然后取最小显然不可取，可以采取如下考虑：

首先答案等于每一排的答案相加，每一排的答案都是独立的

对于每一排来说，当考虑完了当前这一排的所有元素作为排头时需要用多少步然后取最小即可

那如何考虑呢？

置一cnt[n]数组，cnt[i]表示第i行的这个元素如果放在第一行要用多少步，初始全部置为i-1+n,取最坏情况，然后遍历一遍这一排数组元素，如果是在1~n*m中间，那ok，算一下它是哪一个元素放在第一行时，然后，它是在这个位置正确的，然后cnt[i]--

至于怎么算，留给读者，应该不难，要注意一些细节

#include<bits/stdc++.h>
#define ll long long
#define rg register ll
using namespace std;
ll n,m,ans;
int main()
{
    cin>>n>>m;
    vector<vector<ll>>v(n+1,vector<ll>(m+1));
    for(rg i=1;i<=n;i++)
    {
        for(rg j=1;j<=m;j++)
        {
            cin>>v[i][j];
        }
    }
    for(rg j=1;j<=m;j++)
    {
        vector<ll>tep(n+1);
        tep[0]=n;
        for(rg k=1;k<=n;k++)
        {
            tep[k]=k+n;
        }
        for(rg k=1;k<=n;k++)
        {
            if(v[k][j]>=1&&v[k][j]<=n*m)
            {
                if(v[k][j]%m==j)
                {
                    ll check=k-(v[k][j]/m+1);
                    if(check<0)check+=n;
                    tep[check]--;
                }
                else if(v[k][j]%m==0&&j==m)
                {
                    ll check=k-(v[k][j]/m);
                    if(check<0)check+=n;
                    tep[check]--;

                    
                }
            }
        }
        /*for(auto it :tep)cout<<it<<endl;
        cout<<endl;*/
        ans+=*min_element(tep.begin(),tep.end());
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
    while(1)getchar();
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/01/24 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度