首页 > 其他 > 详细

Codeforces Global Round 9 D. Replace by MEX

时间:2020-07-07 00:12:20      阅读:42      评论:0      收藏:0      [点我收藏+]

题目链接:https://codeforces.com/contest/1375/problem/D

题意

给出一个大小为 $n$,元素值位于 $[0,n]$ 之间的数组,每次可以将一个元素替换为数组中未出现过的最小非负整数,最多替换 $2n$ 次,输出一种使得数组为非递减数组的替换方案。

题解

将数组替换为 $0, 1, 2, \dots, n - 1$ 即可,每个 $a_i$ 最多替换两次,一次为 $n$,一次为 $i$ 。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

int n, a[N];

int MEX() {
    int cnt[n + 1] = {};
    for (int i = 0; i < n; i++)
        ++cnt[a[i]];
    for (int i = 0; i <= n; i++)
        if (cnt[i] == 0) return i;
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<int> res;
    while (!is_sorted(a, a + n)) {
        int mex = MEX();
        if (mex == n) {
            for (int i = 0; i < n; i++) {
                if (a[i] != i) {
                    a[i] = n;
                    res.push_back(i);
                    break;
                }
            }
        } else {
            a[mex] = mex;
            res.push_back(mex);
        }
    }
    cout << res.size() << "\n";
    for (auto i : res) cout << i + 1 <<  ;
    cout << "\n";
}

int main() {
    int t; cin >> t;
    while (t--) solve();
}

 

Codeforces Global Round 9 D. Replace by MEX

原文:https://www.cnblogs.com/Kanoon/p/13258198.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!