codeforces-GlobalRound9-D

codeforces-GlobalRound9-D

七月 08, 2020

D.Replace by MEX

题意:

你被给予了一个数组，包含n个[0, n]的整数。每一次操作，你可以选择数组中的一个元素替换成这个数组的MEX。
例如，如果数组是[0, 2, 2, 1, 4]，你可以选择第二个元素替换成整个数组元素的MEX，数组会变成[0, 3, 2, 1, 4]。
MEX的定义为不包含这个于这个数组的最小的非负整数。

分析:
首先，题目给出操作的次数最多为2n次，这是不是暗示我们先把数组通过n次变成一个样子，再通过n次变成另一个样子？我们把ai≠i称之为一个未修复点，我们可以进行如下的操作来修复每一个点。
1.如果mex = n，我们就任意地替换一个未修复点。
2.如果mex < n，我们就替换下标是mex的点。
这两个操作最多2n次，每一次操作可以使得未修复的点减少一次。
为什么这么做呢？因为每次如果求出一个mex = n的时候，就可以使得下一次修复的时候，mex < n。我们的目的就是为了修复一个点的时候，让mex < n，这样可以正常的修复。求mex是线性的。

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
82
83
84
85
86
# include <bits/stdc++.h>

using namespace std;
typedef long long ll;

# define endl '\n'

# define Turnoff std::ios::sync_with_stdio(false)

const int Max=1e3+5;
const int Mod=1e7+7;
int data[Max],cnt[Max];
bool vis[Max];

int main() {
    Turnoff;
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        for(int i=0;i<=n;i++)cnt[i]=0;
        for(int i=1;i<=n;i++){
            cin>>data[i];
            cnt[data[i]]++;
            vis[i]=0;
        }
        int ti=2*n;
        vector<int>ops;
        bool check=0;
        while(ti){///最多2n次让原数组变成1 2 3 4 5.....
            int num;bool ok=1;
            for(int i=0;i<=n;i++){
                if(cnt[i]){
                    if(cnt[i]>1)check=1;
                    continue;
                }
                num=i;break;
            }
            if(check){///把每个数组中的数都变成只出现一次的数 其实没必要
                bool flag=1;
                for(int i=1;i<=n;i++){
                    if(cnt[data[i]]>1){
                        cnt[data[i]]--;
                        cnt[num]++;ti--;
                        data[i]=num;flag=0;
                        ops.push_back(i);
                        break;
                    }
                }
                if(flag)check=0;
            }
            ///每求出一个mex==0 替换一个data[num]!=num的数之后mex必然>0 即每个位置最多被操作两次
            else{
                if(num){///如果不是0 将下标为num的改为num 之后这个位置的数不会在变化
                    vis[num]=1;
                    cnt[data[num]]--;
                    data[num]=num;
                    cnt[num]++;
                    ops.push_back(num);
                    ti--;
                }
                else{///如果是0则选择一个data[num]!=num的数 替换
                    for(int i=1;i<=n;i++){
                        if(vis[i])continue;
                        cnt[data[i]]--;
                        data[i]=num;
                        cnt[num]++;ti--;
                        ops.push_back(i);
                        break;
                    }
                }
            }
            for(int i=1;i<=n;i++){
                if(data[i]<data[i-1]){
                    ok=0;
                    break;
                }
            }
            if(ok)break;
        }
        //for(int i=1;i<=n;i++)cout<<data[i]<<" ";
        //cout<<endl;
        cout<<ops.size()<<endl;
        for(auto i:ops)cout<<i<<" ";
        cout<<endl;
    }
}