题目描述
大致题意就是序列是范围在 0~n,每次可以操作一个数使得它的值+1,现在问你
操作几次后mex 为0~n,输出n+1个操作
样例
5
3
0 1 3
7
0 1 2 3 4 3 2
4
3 0 0 0
7
4 6 2 3 5 0 5
5
4 0 1 0 4
算法1
(暴力枚举) $O(nt)$
直观想一下 对于凑MEX=i时 假如 0~i-1凑出来的代价已经算好了为now 那么凑i的代价只需要加
i的个数a[i]就行 ans[i]=now+a[i];
于是问题转化为怎么算凑0~i-1的代价
我们运用数学归纳的思想
假如a[i]有值 i可以拿出a[i]-1个数来存起来方便之后凑某个数用
假如a[i]等0 我们用存起来的最后一个数v.back()得i的代价为i-v.back()!然后弹出
这样就可以了 某个数凑不出就break
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define read(x) scanf("%lld",&x)
const int N =2e5+10;
int a[N];
void sol()
{
int n;
read(n);
rep(i,1,n)
{
int x;
read(x);
a[x]++;
}
vector<int>s;
int ans[N];
int now=0;
int idx=0;
rep(i,0,n)
{
ans[i]=now+a[i];
if(!a[i]){
if(s.size()) {now+=i-s.back();s.pop_back();}
else {idx=i+1;break;}
}
rep(j,1,a[i]-1) s.push_back(i);//多余的存起来,方便后面得到某个数
}
rep(i,idx,n) ans[i]=-1;
rep(i,0,n) printf("%lld ",ans[i]),a[i]=0;
puts("");
}
signed main()
{
int t;read(t);
while(t--) sol();
}