CF1942B Bessie and MEX 题解

题目简述

给定一个长度为 $n$ 的数组 $a$，让你构造一个等长的排列 $p$，其中从 $0$ 到 $n-1$ 的每个整数恰好出现一次。满足对于每一个位置 $a_i=\texttt{MEX}(p_1,p_2, \ldots, p_i) - p_i$，其中数组的 $\texttt{MEX}$ 是不在该数组中出现的最小非负整数。

题目分析

我们发现正着做并不是十分好做，依据正难则反的思想，我们考虑倒着做。

我们首先考虑构造 $p_n$。为了方便一些，我们令 $mex_i=\texttt{MEX}(p_1, p_2, \ldots, p_i)$。因为 $p$ 是一个从 $0$ 到 $n-1$ 的排列，所以 $mex_n=n$，由于 $a_i=mex_i-p_i$，所以可以推出 $p_n=mex_n-a_n$，这样我们就知道了 $p_n$ 的值。对于其他的 $p_i$，我们也可以效仿这种方法。现在，我们只需要知道 $mex_i$ 就可以了。

我们考虑如何求解 $mex_i$，首先，我们求 $p_i$ 的值的时候，肯定已经知道了 $p_{i+1} \sim p_n$ 的值了，由于 $p$ 是一个排列，所以在 $p_1 \sim p_i$ 中 $p_{i+1} \sim p_n$ 一定没有出现过且不可能出现大于 $p_{i+1} \sim p_n$ 的数，再根据 $\texttt{MEX}$ 的定义，我们便可知 $mex_i=\min_{i+1 \leq j \leq n~}{p_j}$。然后这道题就做完了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int T,n,a[N],p[N],mex;
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	} 
	mex=n;
	for(int i=n;i>=1;i--)
	{
		p[i]=mex-a[i];
		mex=min(p[i],mex);
	}
	for(int i=1;i<=n;i++)
	{
		cout<<p[i]<<" ";
	}
	cout<<"\n";
	return;
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
    	solve();
	}
	return 0;
}