定州网站建设开发网站的公司

Problem - C - Codeforces

题目大意：有一个长度为n的数组，数组中每个数字互不相同，范围都是0到n，每次操作将每一个数字从左到右依次变成当前数组的MEX，问k次操作后的数组

1<=n<=1e5；1<=k<=1e9

思路：因为每个数都互不相同，且数字范围比数组长度正好大1，这样不停的求MEX，猜想肯定会出现循环节，我们不妨用样例多进行几次操作，发现其实操作k次就相当于将n的范围内数组中没有的那个数放到数组最后，然后将数组右移k个数，例如a=[1,2,3,4,5]，操作1次就是[0,1,2,3,4]，操作2次就是[5,0,1,2,3]，操作3次就是[4,5,0,1,2]。

所以我们将0~n内数组中没出现的那个数放到数组末尾，然后令k对(n+1）取模，先输出[n+1-k+1,n+1]部分的数组，再输出[1,n-k]部分的数组

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
int a[N];
int cnt[N];
void init()
{for (int i = 0; i <= n; i++){cnt[i] = 0;}
}
void solve()
{int k;cin >> n >> k;init();int mex = 0;for (int i = 1; i <= n; i++){cin >> a[i];cnt[a[i]]++;//记录每个数字是否出现}for (int i = 0; i <= n; i++){if (!cnt[i]){mex = i;//找到当前的MEXbreak;}}a[n + 1] = mex;k = k % (n + 1);for (int i = n + 1 - k + 1; i <= n + 1; i++){cout << a[i] << " ";}for (int i = 1; i <= n - k; i++){cout << a[i] << " ";}cout << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--){solve();}
}