题意

给你个数列，让你求对应下标i使得整个数列MEX（i）的最小步数，其中MEX（i）是指出现的最小正整数.

题解：

首先计数把每个数字出现的次数记录，对于下标i，我们需要让0-i-1的数至少出现一次，然后让数字i全体加1，这里用动态规划的思想，假设dp[i]是使得数列出现0-i每个至少一个的最小步数 那么 ans[i+1]=dp[i]+cnt[i+1]，此时满足0-i至少出现一次，且所有等于i+1的值都被加1，MEX就位i+1，对于dp的转移来说，dp[i+1]=dp[i]+（i+1- 数组中最接近i+1的一个数字），这里可以用优先队列处理，事实上我们会发现数一定是从小到大所以用栈也是可以处理的。具体的做法是，转移后，将i都推入优先队列或栈中，作为最接近i+1的一个备选答案，如果栈空说明个数不够，输出-1，随后所有数都不可能成立。更进一步的，发现dp只会用到上一个状态，那用一个变量记录即可。

#include<bits/stdc++.h>
using namespace std;
long long cnt[200005];
void slove()
{int n;cin>> n;for (int i = 0; i <=n; i++)cnt[i] = 0;for (int i = 0; i < n; i++){int t;cin >> t;cnt[t]++;}long long s = 0;//s代表dp[i-1];priority_queue<long long>q;for (int i = 0; i <= n; i++){printf("%lld ", max((long long)-1, s + cnt[i]));//输出ans[i]=dp[i-1]+cnt[i]while (cnt[i]--)q.push(i);//这些数可以作为后续转移答案if (!q.empty()){s += i - q.top();//dp[i]=dp[i-1]+（i- 数组中最接近i的一个数字)q.pop();//该数已被占用，不可重复使用。}else s = -1e18;}puts("");
}
int main()
{int t;cin >> t;while(t--)slove();
}