D. Permutation Addicts codefoeces1738D

Problem - D - Codeforces

题目大意：有一整数k，a数组是一个n的排列，按如下两个规则变为b数组：规则1：如果ai<=k,b[a[i]]=在当前i左边最近的>k的数，如果不存在这样的数，b[a[i]]=n+1。规则2：如果ai>k,b[a[i]]=在当前i左边最近的<=k的数，如果不存在这样的数则=0。现给出b数组，求k和a数组

0<=k<=n;1<=n<=1e5

思路：首先我们可以根据这两条规则将所有数分成两类，一种是<=k的数，另一种是>k的数，那么想要求出k我们只需要找到<=k的数的最大值，而对于这样的a[i],b[a[i]]都会是比其更大的数，所以我们在遍历b数组时找到i<=b[i]的位置，记录i的最大值即可得到k。

然后我们考察b数组怎么还原a数组，我们发现对于b数组，如果bi!=n+1或,那么bi在a数组中一定在i左边，因为在a构造b时无论规则1还是2都是去左边找这个数，又因为a数组是n的排列，也就是数字不重复，所以我们只要找到a中数字的顺序即可，那么我们可以把a数组看成一个森林，如果bi=n+1或0，那么可知他们是不满足规则12的前半部分的，也就是无法得知i在a中左边的数，所以可以把这样的i设为树的根节点，对于其他的数，我们从bi到i建一条边，表示bi在i的左边，比如b数组=6,4,4,1,1时得到的树如下

构建好树以后，我们可以按bfs序输出每个点，但要注意在每一层输出前要按点的子节点数进行排序，因为2,3的左边第一个数只能是4而不能是5，我们要先把5这样没有子节点的数输出，这样就能使有子节点的数和他的子节点按照相邻的格式输出

#include
#include
#include
#include
#include
using namespace std;
const int N = 1e5 + 5;
vector<int>v[N];//邻接表存图
bool cmp(int a, int b)
{
	return v[a].size() < v[b].size();
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		scanf("%d", &n);		
		for (int i = 0; i <= n; i++)
		{
			v[i].clear();
		}
		int k = 0;//如果a中没有<=k的数，k=0
		queue<int>q;
		for (int i = 1; i <= n; i++)
		{
			int x;
			scanf("%d", &x);
			if (x == n + 1 || x == 0)
			{//无法确定左边的数的点就是根节点，因为可能有多个根节点，所以用一个超级根连接所有根节点
				v[0].push_back(i);
			}
			else
			{//b[i]到i建边表示a中b[i]在i左边
				v[x].push_back(i);
			}	
			if (i <= x)
			{//k的值等于b中i<=b[i]的i的最大值
				k = max(k, i);
			}
		}
		printf("%d\n", k);
		q.push(0);//从超级根开始bfs
		while (!q.empty())
		{			
			int u = q.front();
			q.pop();
			if(u!=0)
				printf("%d ", u);
			if(!v[u].empty())//将所有子节点按照他们的子节点数量排序
				sort(v[u].begin(), v[u].end(), cmp);
			for (int j = 0; j < v[u].size(); j++)
			{
				q.push(v[u][j]);
			}
		}
		printf("\n");
	}
	return 0;
}