Codeforces 1294E Obtain a Permutation 题解

发表于 | 阅读次数：
本文字数： 793 字 | 阅读时长 ≈ 3 分钟

题意简述

有一个$n$行$m$列的矩阵$a$，每次你可以做两个操作：

  1. 改变某一个元素的值
  2. 对某一列做一次循环位移
    然后你要使得每个i,j满足$a[i][j]=(i-1)\times n+j$。问最少需要多少次操作
    $n\times m<=2e5$，元素值域为$[1,2e5]$

思路框架

列之间显然是不影响的。考虑每列单独出来考虑。接下来都是在列里面讨论问题的。

像这种问“循环位移需要多少次操作”的题目，一般要设一个数组$move[i]$表示移动$i$次能有多少匹配。这个很好处理，对于每个数，我们找到它应该在哪个位置，和它实际所在的位置相减去绝对值，设为$d$。那么$move[d]$++。其原因是，当前的这个数移动$d$次就到了它该在的地方，所以就给$move[d]$贡献了一个答案。$O(n)$就能预处理一遍。

然后我们枚举移动了多少下。移动$i$下之后，花费$i$的代价，能匹配上$move[i]$个。但是还剩下$n-move[i]$个，就需要用操作$1$来直接修改，花费的代价就是$n-move[i]$。
总代价就是$i+n-move[i]$。然后枚举$i$从$1$到$n$，取最小即珂。

每一列都这样求一遍答案，把答案加起来，就是总答案了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 255555
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }

    vector<int> a[N];
    int n,m;
    void Input()
    {
        Rd(2,&n,&m);
        F(i,0,n-1) 
        {
            a[i].push_back(0);
            F(j,1,m) {int x;R1(x);a[i].p_b(x);}
        }
    }

    int move[N];
    int calc(int col) //求第col列的答案
    {
        F(i,0,n-1) move[i]=0; //记得清空
        //不要用memset，万一n=1，m=1e5，就浪费时间了！
        F(i,0,n-1) 
        {
            int u=a[i][col]-col; 
            //在第col列的满足条件的数有一个共同点，就是它%m==col。
            if (u%m==0) if (0<=u/m and u/m<n) ++move[(i-u/m+n)%n];
            //先判断它是否珂能属于这一列，然后计算它移动多少步能归位
        }
        
        int ans=0x3f3f3f3f;
        F(i,0,n) ans=min(ans,i+n-move[i]); 
        return ans;
    }
    void Soviet()
    {
        int ans=0;
        F(i,1,m) ans+=calc(i);
        printf("%d\n",ans);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main(){
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w