首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Codeforces Round #615 (Div. 3) E. Obtain a Permutation

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

作者头像
glm233
发布2020-09-28 11:11:03
2940
发布2020-09-28 11:11:03
举报

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 条评论
热度
最新
推荐阅读
目录
  • E. Obtain a Permutation
    • 题目链接:https://codeforces.com/contest/1294/problem/E
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档