参考:Codeforces Round #615 (Div. 3) Editorial
其实这个算法的本质也就是暴力,只不过是更为有效的暴力
每一列之间不互相影响,那么只需要求出每一列的最小值即可
对于每一列:进行贪心,具体的贪心代码:
vector<int> cnt(n+5);
for(int j=1;j<=n;++j)
if(a[j][i]%m==i-1) //是否属于该列
{
int pos=a[j][i]/m; //属于该列上第几个位置
if(pos<n) cnt[(j-pos-1+n)%n]++; //属于某一个循环层
}
int t=inf;
for(int j=0; j<=n-1; ++j)
t=min(t,n-cnt[j]+j);
代码:
// Created by CAD on 2020/1/25.
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,m; cin>>n>>m;
vector<vector<int> > a(n+5,vector<int>(m+5));
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
cin>>a[i][j],a[i][j]--;
int ans=0;
for(int i=1;i<=m;++i)
{
vector<int> cnt(n+5);
for(int j=1;j<=n;++j)
if(a[j][i]%m==i-1)
{
int pos=a[j][i]/m;
if(pos<n) cnt[(j-pos-1+n)%n]++;
}
int t=inf;
for(int j=0; j<=n-1; ++j)
t=min(t,n-cnt[j]+j);
ans+=t;
}
cout<<ans<<endl;
return 0;
}
原文链接: https://www.cnblogs.com/cader/p/12233378.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/324828
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!